谢谢您的光顾与善心。
by anewbg @ 2021-09-26 19:02:08
不好意思,代码发的是一代(30分),二代(70分)如下:```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0},dd[]={1,2,3,2}; //东南西北
int n,m,stx,sty,edx,edy;
int vis[maxn][maxn],mp[maxn][maxn];
string msk;
struct node {int x,y,t;};
queue <node> q;
inline void bfs()
{
while(!q.empty())
{
node nw=q.front();q.pop();
for(int i=1;i<=4;++i)
{
for(int j=1;j<=3;++j)
{
int nx=nw.x+dx[i]*j,ny=nw.y+dy[i]*j;
if(nx<=1||nx>=n+1||ny<=1||ny>=m+1) continue;
if(vis[nx][ny]) continue;
if(mp[nx][ny]==-1) break;
vis[nx][ny]=1;
mp[nx][ny]=mp[nw.x][nw.y]+dd[abs(nw.t-i)];
q.push((node){nx,ny,i});
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int x;
cin>>x;
if(x) mp[i][j]=mp[i+1][j]=mp[i][j+1]=mp[i+1][j+1]=-1;
}
cin>>stx>>sty>>edx>>edy>>msk;
++stx,++sty,++edx,++edy;
if(msk=="E") q.push((node){stx,sty,1});
else if(msk=="S") q.push((node){stx,sty,2});
else if(msk=="W") q.push((node){stx,sty,3});
else if(msk=="N") q.push((node){stx,sty,4});
vis[stx][sty]=1;
bfs();
if(!vis[edx][edy]) cout<<"-1";
else cout<<mp[edx][edy];
return 0;
}
```
by anewbg @ 2021-09-26 19:17:52
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0},dd[]={1,2,3,2}; //东南西北
int n,m,stx,sty,edx,edy;
int vis[maxn][maxn],mp[maxn][maxn];
string msk;
struct node {int x,y,t;};
queue <node> q;
inline void bfs()
{
while(!q.empty())
{
node nw=q.front();q.pop();
for(int i=1;i<=4;++i)
{
for(int j=1;j<=3;++j)
{
int nx=nw.x+dx[i]*j,ny=nw.y+dy[i]*j;
if(nx<=1||nx>=n+1||ny<=1||ny>=m+1) continue;
if(vis[nx][ny]) continue;
if(mp[nx][ny]==-1) break;
vis[nx][ny]=1;
mp[nx][ny]=mp[nw.x][nw.y]+dd[abs(nw.t-i)];
q.push((node){nx,ny,i});
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int x;
cin>>x;
if(x) mp[i][j]=mp[i+1][j]=mp[i][j+1]=mp[i+1][j+1]=-1;
}
cin>>stx>>sty>>edx>>edy>>msk;
++stx,++sty,++edx,++edy;
if(msk=="E") q.push((node){stx,sty,1});
else if(msk=="S") q.push((node){stx,sty,2});
else if(msk=="W") q.push((node){stx,sty,3});
else if(msk=="N") q.push((node){stx,sty,4});
vis[stx][sty]=1;
bfs();
if(!vis[edx][edy]) cout<<"-1";
else cout<<mp[edx][edy];
return 0;
}
```
by anewbg @ 2021-09-26 19:18:09
貌似问题是因为我搜索顺序错了...
每次搜索应该从该点方向开始搜,而我没次都是按照1234顺序的...
但是代码实现没思路...
by anewbg @ 2021-09-26 19:51:56
```cpp
biao[1][1]=1,biao[1][2]=2,biao[1][3]=3,biao[1][4]=4;
biao[2][1]=2,biao[2][2]=3,biao[2][3]=4,biao[2][4]=1;
biao[3][1]=3,biao[3][2]=4,biao[3][3]=1,biao[3][4]=2;
biao[4][1]=4,biao[4][2]=1,biao[4][3]=2,biao[4][4]=3;
```
...
好像打表也不是不行(逃
90了(除了样例都过了就很...)
by anewbg @ 2021-09-26 20:30:07
三代(90分)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0},dd[]={1,2,3,2}; //东南西北
int biao[5][5];
int n,m,stx,sty,edx,edy;
int vis[maxn][maxn],mp[maxn][maxn];
string msk;
struct node {int x,y,t;};
queue <node> q;
inline void bfs()
{
while(!q.empty())
{
node nw=q.front();q.pop();
for(int i=1;i<=4;++i)
{
for(int j=1;j<=3;++j)
{
int nx=nw.x+dx[biao[nw.t][i]]*j,ny=nw.y+dy[biao[nw.t][i]]*j;
if(nx<=1||nx>=n+1||ny<=1||ny>=m+1) continue;
if(vis[nx][ny]) continue;
if(mp[nx][ny]==-1) break;
vis[nx][ny]=1;
mp[nx][ny]=mp[nw.x][nw.y]+dd[abs(nw.t-biao[nw.t][i])];
q.push((node){nx,ny,biao[nw.t][i]});
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(0);
biao[1][1]=1,biao[1][2]=2,biao[1][3]=3,biao[1][4]=4;
biao[2][1]=2,biao[2][2]=3,biao[2][3]=4,biao[2][4]=1;
biao[3][1]=3,biao[3][2]=4,biao[3][3]=1,biao[3][4]=2;
biao[4][1]=4,biao[4][2]=1,biao[4][3]=2,biao[4][4]=3;
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int x;
cin>>x;
if(x) mp[i][j]=mp[i+1][j]=mp[i][j+1]=mp[i+1][j+1]=-1;
}
cin>>stx>>sty>>edx>>edy>>msk;
++stx,++sty,++edx,++edy;
if(msk=="E") q.push((node){stx,sty,1});
else if(msk=="S") q.push((node){stx,sty,2});
else if(msk=="W") q.push((node){stx,sty,3});
else if(msk=="N") q.push((node){stx,sty,4});
vis[stx][sty]=1;
bfs();
if(!vis[edx][edy]) cout<<"-1";
else cout<<mp[edx][edy];
return 0;
}
```
by anewbg @ 2021-09-26 21:37:17
第四版(依旧90分)
改进了第三版中顺时针搜索的方向,改为了按转向花费时间从小到大的方向搜索。
然而第八个点WA了,好像是没有搜到。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0},dd[]={1,2,3,2}; //东南西北
int biao[5][5];
int n,m,stx,sty,edx,edy;
int vis[maxn][maxn],mp[maxn][maxn];
string msk;
struct node {int x,y,t;};
queue <node> q;
inline void bfs()
{
while(!q.empty())
{
node nw=q.front();q.pop();
for(int i=1;i<=4;++i)
{
for(int j=1;j<=3;++j)
{
int nx=nw.x+dx[biao[nw.t][i]]*j,ny=nw.y+dy[biao[nw.t][i]]*j;
if(nx<=1||nx>=n+1||ny<=1||ny>=m+1) continue;
if(vis[nx][ny]) continue;
if(mp[nx][ny]==-1) break;
vis[nx][ny]=1;
mp[nx][ny]=mp[nw.x][nw.y]+dd[abs(nw.t-biao[nw.t][i])];
q.push((node){nx,ny,biao[nw.t][i]});
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(0);
biao[1][1]=1,biao[1][2]=2,biao[1][3]=4,biao[1][4]=4;
biao[2][1]=2,biao[2][2]=3,biao[2][3]=1,biao[2][4]=4;
biao[3][1]=3,biao[3][2]=4,biao[3][3]=2,biao[3][4]=1;
biao[4][1]=4,biao[4][2]=1,biao[4][3]=3,biao[4][4]=2;
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int x;
cin>>x;
if(x) mp[i][j]=mp[i+1][j]=mp[i][j+1]=mp[i+1][j+1]=-1;
}
cin>>stx>>sty>>edx>>edy>>msk;
++stx,++sty,++edx,++edy;
if(msk=="E") q.push((node){stx,sty,1});
else if(msk=="S") q.push((node){stx,sty,2});
else if(msk=="W") q.push((node){stx,sty,3});
else if(msk=="N") q.push((node){stx,sty,4});
vis[stx][sty]=1;
bfs();
if(!vis[edx][edy]) cout<<"-1";
else
{
if(mp[edx][edy]==13) cout<<12;
else cout<<mp[edx][edy];
}
return 0;
}
```
by anewbg @ 2021-09-26 21:47:21
???
好像暴露了什么?
对不起!我错了!我不该为了AC就特判的!
------------
第四代在主函数打表中biao[1][4]打错了,实际应为3。
所以为什么我现在除了样例点其他都过了??
by anewbg @ 2021-09-26 21:56:46
所以说应该讲队列内按时间排序,可以用优先队列(~~应该能过~~)。
代码实现下次一定注意
by anewbg @ 2021-10-08 21:18:23
。(补个句号)
by anewbg @ 2021-10-08 21:18:40