hdu 1242,一直wa，请高手指教。我想知道具体哪个环节错了。
http://acm.hdu.edu.cn/showproblem.php?pid=1242
#include<iostream>
#include<queue>
using namespace std;
char map[201][201];
int visit[201][201];
struct node{
int x,y,step;
}fri[40001];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n;
bool flag;
node di;
int dfs(int si,int sj)
{
queue<node>q;
node front,next;
front.x=si;front.y=sj;
front.step=0;
while(!q.empty())q.pop();
q.push(front);
while(!q.empty())
{
front=q.front();
q.pop();
if(front.x==di.x&&front.y==di.y)
{ di.step=front.step;
flag=1;
break;
}
int xx,yy;
for(int i=0;i<4;i++)
{
xx=front.x+dir[i][0];
yy=front.y+dir[i][1];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&!visit[xx][yy]&&map[xx][yy]!='#')
{
visit[xx][yy]=1;
next.x=xx;
next.y=yy;
next.step=front.step+1;
if(map[xx][yy]!='.'&&map[xx][yy]!='a')next.step=next.step+1;
q.push(next);
}
}
}
return 0;
}
int main()
{ flag=0;
int result,i,j,k;
k=0;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='r')
{
fri[k].x=i;
fri[k].y=j;
k++;}
else if(map[i][j]=='a')
{
di.x=i;
di.y=j;
}
}
result=99999;
for(i=0;i<k;i++)
{
memset(visit,0,sizeof(visit));
dfs(fri[i].x,fri[i].y);
if(result>di.step)result=di.step;
}
if(flag)
cout<<result<<endl;
else
cout<<"Poor ANGEL has to stay in the prison all his life." <<endl;
}
return 0;
}
[解决办法]
‘x’代表警卫 你都没判断
[解决办法]
用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
A*算法
SPFA算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法
[解决办法]
你在队列里面while找到了目标之后，你就break，难道你觉得那肯定就是最短路径？明显逻辑的问题。还有这里的函数定义名称写成dfs，是在误导读者么？
PS：哥，你的代码能够贴好看点吗？
/*codes here！！！*/
