5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
思路:如果正向搜索,需要逆向输出,因此采用逆向搜索,并记录前驱。DFS会超时。#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX = 105;
struct Pos
{
int x, y, time;
friend bool operator< (Pos a, Pos b)
{
return a.time > b.time;
}
};
struct Pre//记录前驱
{
int x, y;
}pre[MAX][MAX];
int N, M, vis[MAX][MAX];
char Map[MAX][MAX];
int x_x[4] = {-1, 0, 1, 0};//四方向搜索
int y_y[4] = {0, 1, 0, -1};
int main()
{
while(scanf("%d %d", &N, &M) != EOF)
{
memset(vis, 0, sizeof(vis));
priority_queue <Pos> que;
for(int i = 0;i < N; ++i) scanf("%s", Map[i]);
Pos top, next;
pre[N-1][M-1].x = -1;
top.x = N-1;
top.y = M-1;
if(Map[N-1][M-1] == '.') top.time = 0;//出口位置可能不是'.'
else top.time = Map[N-1][M-1]-'0';
que.push(top);
vis[N-1][M-1] = 1;
bool Find = false;
while(!que.empty())
{
top = que.top();
que.pop();
if(top.x == 0 && top.y == 0)
{
Find = true;
printf("It takes %d seconds to reach the target position, let me show you the way.\n", top.time);
int x = 0, y = 0, step = 1;
while(pre[x][y].x != -1)//搜前驱,直到找到终点
{
int tx = pre[x][y].x;
int ty = pre[x][y].y;
printf("%ds:(%d,%d)->(%d,%d)\n", step++, x, y, tx, ty);
if(Map[tx][ty] != '.')
{
int k = Map[tx][ty]-'0';
for(int j = 0;j < k; ++j) printf("%ds:FIGHT AT (%d,%d)\n", step++, tx, ty);
}
x = tx;
y = ty;
}
break;
}
else
{
for(int i = 0;i < 4; ++i)//四方向搜索
{
next.x = top.x+x_x[i];
next.y = top.y+y_y[i];
if(next.x < 0 || next.y < 0 || next.x >= N || next.y >= M) continue;
if(vis[next.x][next.y] || Map[next.x][next.y] == 'X') continue;
vis[next.x][next.y] = 1;
if(Map[next.x][next.y] == '.') next.time = top.time+1;
else next.time = top.time+1+Map[next.x][next.y]-'0';
pre[next.x][next.y].x = top.x;//记录前驱
pre[next.x][next.y].y = top.y;
que.push(next);
}
}
}
if(!Find) printf("God please help our poor hero.\n");
printf("FINISH\n");
}
return 0;
}
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。