用BFS做的，DFS的在这里：逃离迷宫DFS版本
自我感觉广搜的更好理解一点，因为拐弯更好处理。
#include <stdio.h>#include <string.h>#include <queue>using namespace std;int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};char maze[110][110];int vis[110][110];int m,n,k,sx,ex,sy,ey;struct node{int x,y,t;};bool judge(int x,int y)//判断这个格是否符合条件{if(x>=m||y>=n||y<0||x<0||maze[x][y]=='*')return false;return true;}int bfs(){queue <node> q; node a,b;//a用来传递给q，，b用来拓展子节点a.x=sx,a.y=sy,a.t=-1;vis[sx][sy]=1;q.push(a);while(!q.empty()){a=q.front();q.pop();if(a.t>=k)//拐点太多不符合条件,t从-1开始，所以有等于号continue;for(int i=0;i<4;i++){b.x=a.x+dir[i][0];b.y=a.y+dir[i][1];b.t=a.t+1; //拐点加一while(1){if(!judge(b.x,b.y))break;if(b.x==ex&&b.y==ey)return 1;if(!vis[b.x][b.y]){q.push(b); //b是新的就放到q里面vis[b.x][b.y]=1;}b.x+=dir[i][0];b.y+=dir[i][1];}}}return 0;}int main(int argc, char const *argv[]){//freopen("H:\\in.txt","r",stdin);int t;scanf("%d",&t);while(t–){memset(vis,0,sizeof(vis));scanf("%d%d",&m,&n);for(int i=0;i<m;i++)scanf("%s",maze[i]);scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);sx–,ex–,sy–,ey–;//题目是从一开始，我是从零开始if(bfs())printf("yes\n");elseprintf("no\n");}return 0;}
只要心中有希望存在，就有幸福存在。
