难点在于判断转弯小于两次 这个还好
主要是 走过的路还能再走 但是去掉标记数组会超时
*******所以用 v.step<=f[v.x][v.y]即可！！！ 这个思想非常重用！！
查了我一个小时的错误终于找出来了！！！！！！！ ！！！！！
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> using namespace std; int world[1005][1005]; int f[1005][1005]; int dx[4]={0,1,-1,0}; int dy[4]={1,0,0,-1}; int n,m;int sx,sy,ex,ey; struct node { int x,y,d1,chance; node(int x=0,int y=0,int d1=0,int chance=0):x(x),y(y),d1(d1),chance(chance){} }; void bfs() { memset(f,1,sizeof(f)); node u(sx,sy,-1,0); queue<node>q; q.push(u); while(!q.empty()) { node u=q.front();q.pop(); if(u.x==ex&&u.y==ey&&u.chance<=2){printf("YES ");return ;} for(int i=0;i<4;i++) { node v(u.x+dx[i],u.y+dy[i],u.d1,u.chance); if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&((v.x==ex&&v.y==ey)||world[v.x][v.y]==0))//这里(v.x==ex&&v.y==ey)不能改成与目标内容相同！！！ { if(v.d1!=-1) { if(v.d1!=i) { v.chance++;v.d1=i; } } else v.d1=i; if(v.chance>2)continue; if(v.chance<=f[v.x][v.y]) { // printf("%d %d %d ",v.x,v.y,v.chance); f[v.x][v.y]=v.chance; q.push(v); } } } } printf("NO "); } int main() { while(cin>>n>>m,(n+m)) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&world[i][j]); int Q;scanf("%d",&Q); for(int i=1;i<=Q;i++) { scanf("%d%d%d%d",&sx,&sy,&ex,&ey); if(world[sx][sy]!=world[ex][ey]||!world[sx][sy]||!world[ex][ey]||(ex==sx&&sy==ey)) printf("NO "); else bfs(); } } return 0; }
判断条件需谨慎QAQ
时隔一个月重做一遍
当初的代码真是歪歪扭扭 现在看来好尴尬。。。
其实这题不用采用这种转向次数vis就可以过的 后面貌似有一题必须要改变
#include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; #define N 1000+5 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int sx,sy,ex,ey; int n,m; int mp[N][N]; int vis[N][N]; bool inmap(int x,int y) { return x>=1&&x<=n&&y>=1&&y<=m; } struct node { int x,y; int chance;int dic; node(int x,int y,int chance,int dic):x(x),y(y),chance(chance),dic(dic){} }; void bfs() { queue<node>q; node u(sx,sy,2,-1); q.push(u); memset(vis,0,sizeof vis); while(!q.empty()) { node u=q.front();q.pop(); if(u.x==ex&&u.y==ey){printf("YES ");return ;} for(int i=0;i<4;i++) { node v=u; v.x+=dx[i]; v.y+=dy[i]; if(inmap(v.x,v.y)&&!vis[v.x][v.y]&&(mp[v.x][v.y]==0||(v.x==ex&&v.y==ey) ) )//这里要是改成mp[v.x][v.y]==mp[ex][ey]会错 { if(v.dic==-1)v.dic=i; else if(v.dic!=i) { v.dic=i;v.chance--; } if(v.chance<0)continue; q.push(v); vis[v.x][v.y]=1; } } } printf("NO "); } int main() { while(scanf("%d%d",&n,&m),(n+m)) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); int q;cin>>q; while(q--) { scanf("%d%d%d%d",&sx,&sy,&ex,&ey); if(mp[sx][sy]!=mp[ex][ey] ||mp[sx][sy]==0 ) printf("NO "); else bfs(); } } }