#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m; int k,x1,y1,x2,y2,flag; char mp[120][120]; int mark[120][120];//转弯次数 int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; void dfs(int x,int y,int dire) { if(mark[x][y]>k)return; if(x==x2&&y==y2) { if(mark[x][y]<=k)flag=1; return; } if(mark[x][y]==k&&x!=x2&&y!=y2) return; if(flag)return; for(int i=0; i<4; i++) { int nx=x+dir[i][0]; int ny=y+dir[i][1]; if(nx<0||ny<0||nx>=n||ny>=m) continue; if(mp[nx][ny]==‘*‘||mark[nx][ny]<mark[x][y]) //重要剪枝 continue; if(dire!=-1&&i!=dire&&mark[nx][ny]<mark[x][y]+1) continue; mark[nx][ny]=mark[x][y]; if(dire!=-1&&i!=dire) mark[nx][ny]++; dfs(nx,ny,i); if(flag) return; } } int main() { int N; cin>>N; while(N--) { cin>>n>>m; flag=0; for(int i=0; i<n; i++) cin>>mp[i]; cin>>k>>y1>>x1>>y2>>x2; memset(mark,1,sizeof mark); x1--,x2--,y1--,y2--; mark[x1][y1]=0; dfs(x1,y1,-1); if(flag)printf("yes\n"); else printf("no\n"); } return 0; }
原文:http://www.cnblogs.com/gpsx/p/5338923.html