题意 ： 从（0,0）点走到（N-1，M-1）点，问最少时间。
思路 ： BFS、、、、、
#include <stdio.h>
#include <string.h>
#include <queue>
#include <iostream> using namespace std ; struct node
{
int x,y ;
int tim ;
friend bool operator < (node a,node b)
{
return a.tim > b.tim ;
}
} temp,temp1;
int N,M ,t;
char mapp[][] ;
int vis[][] ;
int dir[][] = {{-,},{,},{,-},{,}} ; int BFS()
{
temp.x = ;
temp.y = ;
temp.tim = ;
priority_queue<node>Q ;
Q.push(temp) ;
// vis[0][0] = true ;
while(Q.size())
{
temp = Q.top() ;
Q.pop() ;
if(temp.x == N- && temp.y == M-) return temp.tim ;
for(int i = ; i < ; i++)
{
temp1.x = temp.x+dir[i][] ;
temp1.y = temp.y+dir[i][] ;
if(temp1.x >= && temp1.y >= && temp1.x <= N- && temp1.y <= M- && vis[temp1.x][temp1.y] == - && mapp[temp1.x][temp1.y] != 'X')
{
vis[temp1.x][temp1.y] = temp.x*M+temp.y ;
if(mapp[temp1.x][temp1.y] == '.')
temp1.tim = temp.tim+ ;
else
temp1.tim = temp.tim + mapp[temp1.x][temp1.y]-''+ ;
Q.push(temp1) ;
}
}
}
return - ;
}
void print(int x,int y)
{
if(x == && y == )
return ;
int xx = vis[x][y]/M ;
int yy = vis[x][y]%M ;
print(xx,yy) ;
printf("%ds:(%d,%d)->(%d,%d)\n",t++,xx,yy,x,y) ;
if(mapp[x][y] >= '' && mapp[x][y] <= '')
{
while(mapp[x][y] -'' > )
{
printf("%ds:FIGHT AT (%d,%d)\n",t++,x,y) ;
mapp[x][y] -- ;
}
}
}
int main()
{
while(~scanf("%d %d",&N,&M))
{
for(int i = ; i < N ; i++ )
scanf("%s",mapp[i]) ;
memset(vis,-,sizeof(vis)) ;
int timee = BFS() ;
if(timee == -)
{
printf("God please help our poor hero.\nFINISH\n") ;
}
else
{
t = ;
printf("It takes %d seconds to reach the target position, let me show you the way.\n",timee) ;
print(N-,M-) ;
printf("FINISH\n") ;
}
}
return ;
}