題意：一個N*M的圖，一秒內可上下左右選個方向走一步，一進去，若有數字，就要花數字大小的時間停留在那個格子，輸出從起點(0, 0)到終點(N-1, M-1)每一秒的路徑。
——>>會選擇優先隊列來做就基本上沒問題了。
[cpp] #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100 + 10;
struct node
{
int x;
int y;
int step;
int fax;
int fay;
node(){}
node(int xx, int yy): x(xx), y(yy){}
bool operator < (const node& e) const
{
return step > e.step;
}
void init(int i, int j)
{
x = i;
y = j;
step = fax = fay = -1;
}
}no[maxn][maxn];
char MAP[maxn][maxn];
int N, M, cnt;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
bool bfs()
{
priority_queue<node> pq;
pq.push(no[0][0]);
node temp;
while(!pq.empty())
{
temp = pq.top();
pq.pop();
for(int i = 0; i < 4; i++)
{
int newx = temp.x + dx[i];
int newy = temp.y + dy[i];
if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && no[newx][newy].step == -1)
{
no[newx][newy].step = temp.step + 1;
if(MAP[newx][newy] != '.') no[newx][newy].step += MAP[newx][newy] - '0';
no[newx][newy].fax = temp.x;
no[newx][newy].fay = temp.y;
pq.push(no[newx][newy]);
if(newx == N - 1 && newy == M - 1) return 1;
}
}
}
return 0;
}
void print(node u)
{
if(u.fax == 0 && u.fay == 0)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n", no[N-1][M-1].step);
printf("%ds:(0,0)->(%d,%d)\n", cnt++, u.x, u.y);
for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);
return;
}
print(no[u.fax][u.fay]);
printf("%ds:(%d,%d)->(%d,%d)\n", cnt++, u.fax, u.fay, u.x, u.y);
for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);
}
int main()
{
int i, j;
while(scanf("%d%d", &N, &M) == 2)
{
for(i = 0; i < N; i++)
for(j = 0; j < M; j++)
{
cin>>MAP[i][j];
no[i][j].init(i, j);
}
no[0][0].step = 0;
cnt = 1;
if(bfs()) print(no[N-1][M-1]);
else printf("God please help our poor hero.\n");
printf("FINISH\n");
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100 + 10;
struct node
{
int x;
int y;
int step;
int fax;
int fay;
node(){}
node(int xx, int yy): x(xx), y(yy){}
bool operator < (const node& e) const
{
return step > e.step;
}
void init(int i, int j)
{
x = i;
y = j;
step = fax = fay = -1;
}
}no[maxn][maxn];
char MAP[maxn][maxn];
int N, M, cnt;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
bool bfs()
{
priority_queue<node> pq;
pq.push(no[0][0]);
node temp;
while(!pq.empty())
{
temp = pq.top();
pq.pop();
for(int i = 0; i < 4; i++)
{
int newx = temp.x + dx[i];
int newy = temp.y + dy[i];
if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && no[newx][newy].step == -1)
{
no[newx][newy].step = temp.step + 1;
if(MAP[newx][newy] != '.') no[newx][newy].step += MAP[newx][newy] - '0';
no[newx][newy].fax = temp.x;
no[newx][newy].fay = temp.y;
pq.push(no[newx][newy]);
if(newx == N - 1 && newy == M - 1) return 1;
}
}
}
return 0;
}
void print(node u)
{
if(u.fax == 0 && u.fay == 0)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n", no[N-1][M-1].step);
printf("%ds:(0,0)->(%d,%d)\n", cnt++, u.x, u.y);
for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);
return;
}
print(no[u.fax][u.fay]);
printf("%ds:(%d,%d)->(%d,%d)\n", cnt++, u.fax, u.fay, u.x, u.y);
for(int i = 0; i < MAP[u.x][u.y] - '0'; i++) printf("%ds:FIGHT AT (%d,%d)\n", cnt++, u.x, u.y);
}
int main()
{
int i, j;
while(scanf("%d%d", &N, &M) == 2)
{
for(i = 0; i < N; i++)
for(j = 0; j < M; j++)
{
cin>>MAP[i][j];
no[i][j].init(i, j);
}
no[0][0].step = 0;
cnt = 1;
if(bfs()) print(no[N-1][M-1]);
else printf("God please help our poor hero.\n");
printf("FINISH\n");
}
return 0;
}
