在这博客学的 ttp://www.wutianqi.com/?p=2354
感觉看了这个之后收获良多
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
typedef struct node
{
int x,y,dis;
int prex,prey;
}BFS;
char map[103][103];
BFS path[103][103];
int n,m;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void init()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
path[i][j].dis=-1;
}
bool isok(BFS &b)//这里开始有些疑虑
if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&map[b.x][b.y]!='X')
return 1;
return 0;
}
void output()
{
int i=1,num;
stack<BFS> S;
printf("It takes %d seconds to reach",path[n-1][m-1].dis);
printf(" the target position, let me show you the way.\n");
BFS a,b;
a=path[n-1][m-1];
S.push(a);
while(a.dis!=0)
{
a=path[a.prex][a.prey];
S.push(a);
}
a=S.top();
S.pop();
while(!S.empty())
{
b=S.top();
S.pop();
if(map[b.x][b.y]=='.')
{
printf("%ds:(%d,%d)->(%d,%d)\n",i++,a.x,a.y,b.x,b.y);
a=b;
}
else
{
printf("%ds:(%d,%d)->(%d,%d)\n",i++,a.x,a.y,b.x,b.y);
num=map[b.x][b.y]-'0';
while(num--)
printf("%ds:FIGHT AT (%d,%d)\n",i++,b.x,b.y);
a=b;
}
}
printf("FINISH\n");
}
void bfs()
{
queue<BFS> Q;
BFS a,b;
int i;
a.x=a.y=a.dis=0;
path[0][0]=a;
Q.push(a);
while(!Q.empty())
{
a=Q.front();
Q.pop();
for(i=0;i<4;i++)
{
b.x=a.x+dir[i][0];
b.y=a.y+dir[i][1];
if(!isok(b))
continue;
if(map[b.x][b.y]=='.') //这种的BFS真是high，感觉是个经典题目
b.dis=a.dis+1;
else
b.dis=a.dis+map[b.x][b.y]-'0'+1;
if(b.dis<path[b.x][b.y].dis||path[b.x][b.y].dis==-1)//这里解决了我的担心，我刚看到isok时怕搜索回去。
{
b.prex=a.x;
b.prey=a.y;
path[b.x][b.y]=b;
Q.push(b);//开始时这里忘记了，郁闷！
}
}
}
if(path[n-1][m-1].dis==-1)
printf("God please help our poor hero.\nFINISH\n");
else
output();
}
int main()
{ // freopen("in.txt","r",stdin);
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%s",map[i]);
init();
bfs();
}
return 0;
} 这题值得好好回味！