用bfs进行深搜,求出每个可达点的最小转弯数
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAX_N=105; char g[MAX_N][MAX_N]; int vis[MAX_N][MAX_N]; int n,m; int k,sx,sy,ex,ey; struct node{ int x,y,turns; node(){} node(int cy,int cx,int cturns):x(cx),y(cy),turns(cturns){} }; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; bool judge(int r,int c) { if(1<=r&&r<=m&&1<=c&&c<=n&&g[r][c]=='.') { return true; } return false; } void bfs() { if(sy==ey&&sx==ex) { printf("yes "); return; } queue<node> que; que.push(node(sy,sx,-1)); vis[sy][sx]=1; while(!que.empty()) { node now=que.front();que.pop(); for(int i=0;i<4;i++) { int ny=now.y+dy[i]; int nx=now.x+dx[i]; while(judge(ny,nx))//按一条路深搜 { if(!vis[ny][nx]) { // printf("%c (%d,%d) %d ",g[ny][nx],ny,nx,now.turns+1); que.push(node(ny,nx,now.turns+1)); vis[ny][nx]=1; if(ny==ey&&nx==ex&&now.turns+1<=k) { printf("yes "); return ; } } ny+=dy[i]; nx+=dx[i]; } } } printf("no "); } int main() { int t;scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d %d",&m,&n); scanf("%*c"); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%c",&g[i][j]); } scanf("%*c"); } scanf("%d %d %d %d %d",&k,&sx,&sy,&ex,&ey); bfs(); } return 0; }