我指出了上面提到的问题，更本不可能更新最小时间。因为按照上面的写法，终点只可能入队和出队一次。
然后我又准备用最短路的思想模拟，但是还是准备在上面的基础上改一下，于是每一个点出队我也标记了下，这样保证了终点可以多次遍历到
但是这样一来就无法解决跳出 BFS 问题，于是我想到每一个点最多被上下左右的点走一次，那么是不是标记每一个点最多入队四次就可以了呢？
样例同样出来了，结果还是 WA 。。。
想了下：可能是我虽然标记了入队四次，但是可能这四次都是由同一个点到达的，那么也和标记一次没有分别了，还是无法解决上面的更新最短时间问题。
所以：最终还是只能按照最短路的思想遍历。
很裸的题目了，本来只是打算练下手，结果还是做了很久。菜鸟要努力 Fighting ！！！Come on
code：
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 110;
const int INF = maxn*maxn*10;
int map[maxn][maxn]; //记录图
int vis[maxn][maxn]; //标记入队
char str[maxn];
int n,m;
int dir[4][2] = {0,1, 0,-1, -1,0, 1,0};
//定义优先队列：对于入队了的点,先出队的是时间少的,那么第一个到达终点的就是结果
struct Node{
int x,y; //当前到达的点
int time; //耗费的时间
bool operator < (const Node &b) const{
return b.time < time;
}
};
//每一个点的前驱, 由于是逆向搜索的, 所以记录的其实是当前点的下一个点了
struct Pre{
int px, py;
}pre[maxn][maxn];
void bfs()
{
Node now, next;
priority_queue q;
while(!q.empty()) q.pop();
now.x = n; now.y = m; //从终点走向起点
now.time = map[n][m]; //注意：终点也可能会有怪兽
pre[n][m].px = -1; //输出边界
q.push(now);
memset(vis, 0, sizeof(vis)); //为方便快速输出路径, 从终点往起点找
vis[n][m] = 1; //标记终点入队
while(!q.empty())
{
now = q.top(); q.pop();
if(now.x == 1 && now.y == 1) //一旦到达起点
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n", now.time);
int time = 1;
int x = now.x, y = now.y; //当前的位置
int nx = pre[x][y].px, ny = pre[x][y].py; //下一个位置
while(pre[x][y].px != -1) //不停的找前驱
{
printf("%ds:(%d,%d)->(%d,%d)\n", time++, x-1, y-1, nx-1, ny-1);
while(map[nx][ny]--) //如果有怪兽
{
printf("%ds:FIGHT AT (%d,%d)\n", time++, nx-1, ny-1);
}
x = nx; y = ny; //继续查找下一个点
nx = pre[x][y].px, ny = pre[x][y].py;
}
printf("FINISH\n");
return; //结束
}
for(int i = 0; i < 4; i++)
{
next.x = now.x+dir[i][0];
next.y = now.y+dir[i][1];
if(map[next.x][next.y] >= 0 && !vis[next.x][next.y]) //当前点可以走,并且没有入队过
{
vis[next.x][next.y] = 1; //标记入队
next.time = now.time + 1 + map[next.x][next.y];
pre[next.x][next.y].px = now.x; //前驱记录
pre[next.x][next.y].py = now.y;
q.push(next);
}
}
}
printf("God please help our poor hero.\n"); //不能到达
printf("FINISH\n");
return;
}
int main()
{
while(scanf("%d%d", &n,&m) != EOF)
{
gets(str);
for(int i = 0; i <= n+1; i++) //周围加边
for(int j = 0; j <= m+1; j++)
map[i][j] = -1;
char c;
for(int i = 1; i <= n; i++) //输出的时候注意 -1 处理下
{
for(int j = 1; j <= m; j++)
{
scanf("%c", &c);
if(c != 'X')
{
if(c == '.') map[i][j] = 0;
else map[i][j] = c-'0';
}
}
gets(str);
}
bfs();
}
return 0;
}