题意是要穿过一个迷宫并且将每一步打印出来。
用宽搜的方法找到路径，在 vis 中存一下方向，只是这题被看到的一种不太对的运算符重载坑了很久......
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
char mp[maxn][maxn];
int n,m,t,cnt,vis[maxn][maxn],fight[maxn][maxn];
int dir[][] = {,,,,-,,,-};
struct node
{
int x,y,time;
bool operator<(const node &a) const {
return a.time<time;
}
// 不能用的重载
// friend bool operator < (node a,node b)
// {
// return a.time < b.time;
// }
};
//struct cmp
//{
// bool operator () (node a,node b)
// {
// return a.time < b.time;
// }
//};
bool bfs()
{
priority_queue<node> q;
// priority_queue<node,vector<node>,cmp> q;
node st;
st.x = st.y = st.time = ;
q.push(st);
mp[][] = 'X';
while (!q.empty())
{
node cur = q.top();
q.pop();
if(cur.x==n- && cur.y==m-)
{
t = cur.time;
return true;
}
for(int i = ; i < ; ++i)
{
node next;
next.x = cur.x+dir[i][];
next.y = cur.y+dir[i][];
if(mp[next.x][next.y]=='X') continue;
if(next.x<n && next.x>= && next.y<m && next.y>= )
{
if(mp[next.x][next.y]!='.')
{
next.time = cur.time++mp[next.x][next.y]-'';
fight[next.x][next.y] = mp[next.x][next.y]-'';
}
else next.time = cur.time+;
vis[next.x][next.y] = i+;
q.push(next);
mp[next.x][next.y] = 'X';
}
}
}
return false;
}
void prtmp(int x,int y)
{
if(vis[x][y] == ) return ;
int prex,prey;
prex = x - dir[vis[x][y]-][];
prey = y - dir[vis[x][y]-][];
prtmp(prex,prey);
cout << (cnt++) << "s:(" << prex << "," << prey << ")->(" << x << "," << y << ")\n";
while(fight[x][y]--)
cout << (cnt++) << "s:FIGHT AT (" << x << "," << y << ")\n";
}
int main()
{
while(cin >> n >> m)
{
memset(fight,,sizeof(fight));
memset(vis,,sizeof(vis));
for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j)
cin >> mp[i][j];
if(bfs())
{
cnt = ;
cout << "It takes " << t << " seconds to reach the target position, let me show you the way.\n";
prtmp(n-,m-);
}
else cout << "God please help our poor hero.\n";
cout << "FINISH\n";
}
return ;
}