和连连看非常相似 都是求转向的BFS
改了一下就上交了。。。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> using namespace std; char 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; int k; struct node { int x,y,d,chance; node(int x=0,int y=0,int d=0,int chance=0):x(x),y(y),d(d),chance(chance){} }; void bfs() { memset(f,10,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<=k){printf("yes ");return ;} for(int i=0;i<4;i++) { node v(u.x+dx[i],u.y+dy[i],u.d,u.chance); if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&world[v.x][v.y]=='.')//这里(v.x==ex&&v.y==ey)不能改成与目标内容相同！！！ { if(v.d!=-1) { if(v.d!=i) { v.chance++;v.d=i; } } else v.d=i; if(v.chance>k)continue; if(v.chance<=f[v.x][v.y]) { f[v.x][v.y]=v.chance; q.push(v); } } } } printf("no "); } int main() { int cas;cin>>cas; while(cas--) { cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%s",world[i]+1); } cin>>k>>sy>>sx>>ey>>ex; bfs(); } return 0; }
回顾：
#include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; #define N 1000+5 #define inf 0x3f3f3f3f int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int sx,sy,ex,ey,k; int n,m; char 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,0,-1); q.push(u); memset(vis,inf,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(v.dic==-1)v.dic=i; else if(v.dic!=i) { v.dic=i;v.chance++; } if(v.chance>k)continue; if(inmap(v.x,v.y)&&v.chance<=vis[v.x][v.y]&&mp[v.x][v.y]=='.' )//这里要是改成mp[v.x][v.y]==mp[ex][ey]会错 { q.push(v); vis[v.x][v.y]=v.chance; } } } printf("no "); } int main() { int cas;cin>>cas; while(cas--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex); bfs(); } }