hdu acm 1728题逃离迷宫如何用DFS解决

这题的思路是求出最少的转弯数目，然后和最大的转弯数目比一比，就可以得出答案了，像这种求最少的一般用BFS比较好做的，DFS是解决一些判断定性的问题的。这题用DFS不好做。BFS可以轻松解决。

#include<iostream>

#include<queue>

#include<cstdio>

usingnamespace std;

char map[102][102];

int visit[102][102];

int bx,by,ex,ey,step,N,M;

int XX[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node{int x,y,step,dir;};

void bfs()

{

queue<node>qu;

node t;

int k;

t.x=bx, t.y=by, t.step=0, t.dir=-1;

visit[bx][by]=0;

qu.push(t) ;

while(!qu.empty())

{

t=qu.front();

qu.pop();

for(k=0;k<4;k++)

{

node tt=t;

tt.x+=XX[k][0], tt.y+=XX[k][1];

if(tt.x<1||tt.x>M||tt.y<1||tt.y>N||map[tt.x][tt.y]=='*')

continue;

if(tt.dir!=k&&tt.dir!=-1)tt.step++;

if(tt.step>step)continue;//!!!

if(tt.x==ex&&tt.y==ey)

{

cout<<"yes\n";return;

}

if(visit[tt.x][tt.y]>=tt.step)

{ tt.dir=k;

visit[tt.x][tt.y]=tt.step;

qu.push(tt);

}

}

}

cout<<"no\n";

return ;

}

int main()

{

int CASE,i,j;

cin>>CASE;

while(CASE--)

{

cin>>M>>N;//M行 N列

for(i=1;i<=M;i++)

for(j=1;j<=N;j++)

{

cin>>map[i][j];

visit[i][j]=999;

}

cin>>step>>by>>bx>>ey>>ex;//x对应列

if(bx==ex&&by==ey)

{cout<<"yes\n"; continue;}

bfs();

}

return0;

}