问题描述 公主被魔王feng5166绑架，我们的英雄Ignatius拯救美丽的公主。现在他进入feng5166的城堡。城堡是个大迷宫。只是让问题，我们假设的迷宫是一个n×m的二维数组，左上角是（0,0），右下角是（n-1，m-1）。伊格进入在（0,0），并feng5166的房间的门是在（n-1，m-1），这是我们的目标。在城堡有一些怪物，如果Ignatius遇到他们，他要杀了他们。以下是一些规则： 1。Ignatius只能在四个方向移动（上，下，左，右），每秒一步。一步是定义如下：如果当前位置（x，y），后一步，Ignatius只能站在（X-1，y），（x + 1，y），（x，y-1）或（X，y + 1）。 2数组标有一些字符和数字。我们这样定义他们： 。：Ignatius的地方可以走。 X：这个地方是一个陷阱，Ignatius不应该走上这。 N：这是N惠普怪物（1≤N≤9），如果伊格内修斯走它，他花了N秒杀怪物。 你的任务是给的路径，成本最低秒Ignatius到达目标位置。你可以假设起始位置和目标位置永远不是陷阱，在开始位置永远不会有一个怪物。 输入 输入包含几个测试用例。每个测试案例的第一行包含两个整数n和m（2≤N≤100,2 < = M = 100）指示迷宫的大小。然后一个N×2维数组如下，它描述了整个迷宫。输入由文件结束终止。样品输入的更多细节。 输出 对于每个测试用例，你应该输出“上帝请帮助我们可怜的英雄。“如果Ignatius不能到达目标位置，或你应该输出“n秒达到目标位置，让我带你去。”（n是最低秒），告诉我们的英雄整个路径。在每个测试用例后输出一行包含“完成”。如果有多个路径，任何一个都可以在这个问题上。样本输出的更多细节。 样本输入 5 6 XX。1。 .. x.2。 2…X. …XX。 xxxxx。 5 6 XX。1。 .. x.2。 2…X. …XX。 xxxxx 1 5 6 XX… .. 1。 2…X. …XX。 xxxxx。 示例输出 到达目标位置需要13秒，让我给你指明方向。 1秒：（0,0）->（1,0） 2秒：（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：战斗在（1,4） 9s：战斗在（1,4） 10秒：（1）->（1,5） 11s：（1）->（2,5） 12s：（2,5）->（3,5） 13s：（3,5）->（4,5） 完成 到达目标位置需要14秒，让我给你指明方向。 1秒：（0,0）->（1,0） 2秒：（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：战斗在（1,4） 9s：战斗在（1,4） 10秒：（1）->（1,5） 11s：（1）->（2,5） 12s：（2,5）->（3,5） 13s：（3,5）->（4,5） 14s：打（4,5） 完成 上帝请救救我们可怜的英雄。 完成
下面是我的代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int dx[4] = { 1 , -1 , 0 , 0};
const int dy[4] = { 0 , 0 , 1 , -1};
int row,col,t,flag[105][105],father_dir[105][105];
char a[105][105];
struct node
{
int x;
int y;
int step;
bool operator < (const node n)const
{
return step > n.step;
}
};
void show ( int xx , int yy )
{
int father_x,father_y;
if( xx == 0 && yy == 0 )return ;
father_x = xx - dx[father_dir[xx][yy]];
father_y = yy - dy[father_dir[xx][yy]];
show( father_x , father_y );
if(a[xx][yy] == '.')
{
t++;
printf("ds:(%d,%d)->(%d,%d)\n",t,father_x,father_y,xx,yy);
}
else
{
t++;
printf("%ds:(%d,%d)->(%d,%d)\n",t,father_x,father_y,xx,yy);
int num = a[xx][yy] - '0';
for(int i = 0;i < num;i++)
{
t++;
printf("%ds:FIGHT AT (%d,%d)\n",t,xx,yy);
}
}
}
void bfs()
{
priority_queue<node>p;
node id,ip;
id.x = 0;
id.y = 0;
id.step = 0;
flag[0][0] = 1;
p.push(id);
while(!p.empty())
{
ip = p.top();
p.pop();
if(ip.x == row-1 && ip.y == col-1)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",ip.step);
show(row-1,col-1);
printf("FINISH\n");
return ;
}
for(int i = 0;i < 4;i++)
{
id.x = ip.x + dx[i];
id.y = ip.y + dy[i];
if(id.x >= 0 && id.x < row && id.y >= 0 && id.y < col && flag[id.x][id.y] == 0)
{
if(a[id.x][id.y] == 'X')continue;
else if (a[id.x][id.y] == '.') id.step = ip.step + 1;
else id.step = ip.step + 1 + a[id.x][id.y] - '0';
flag[id.x][id.y] = 1;
father_dir[id.x][id.y] = i;
p.push(id);
}
}
}
printf("God please help our hero!\n");
printf("FINISH\n");
}
int main()
{
while(scanf("%d%d",&row,&col) != EOF)
{
t=0;
memset(flag,0,sizeof(flag));
for(int i = 0;i < row;i++)
scanf("%s",&a[i]);
bfs();
}
return 0;
}
下面是我的代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int dx[4] = { 1 , -1 , 0 , 0};
const int dy[4] = { 0 , 0 , 1 , -1};
int row,col,t,flag[105][105],father_dir[105][105];
char a[105][105];
struct node
{
int x;
int y;
int step;
bool operator < (const node n)const
{
return step > n.step;
}
};
void show ( int xx , int yy )
{
int father_x,father_y;
if( xx == 0 && yy == 0 )return ;
father_x = xx - dx[father_dir[xx][yy]];
father_y = yy - dy[father_dir[xx][yy]];
show( father_x , father_y );
if(a[xx][yy] == '.')
{
t++;
printf("ds:(%d,%d)->(%d,%d)\n",t,father_x,father_y,xx,yy);
}
else
{
t++;
printf("%ds:(%d,%d)->(%d,%d)\n",t,father_x,father_y,xx,yy);
int num = a[xx][yy] - '0';
for(int i = 0;i < num;i++)
{
t++;
printf("%ds:FIGHT AT (%d,%d)\n",t,xx,yy);
}
}
}
void bfs()
{
priority_queue<node>p;
node id,ip;
id.x = 0;
id.y = 0;
id.step = 0;
flag[0][0] = 1;
p.push(id);
while(!p.empty())
{
ip = p.top();
p.pop();
if(ip.x == row-1 && ip.y == col-1)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",ip.step);
show(row-1,col-1);
printf("FINISH\n");
return ;
}
for(int i = 0;i < 4;i++)
{
id.x = ip.x + dx[i];
id.y = ip.y + dy[i];
if(id.x >= 0 && id.x < row && id.y >= 0 && id.y < col && flag[id.x][id.y] == 0)
{
if(a[id.x][id.y] == 'X')continue;
else if (a[id.x][id.y] == '.') id.step = ip.step + 1;
else id.step = ip.step + 1 + a[id.x][id.y] - '0';
flag[id.x][id.y] = 1;
father_dir[id.x][id.y] = i;
p.push(id);
}
}
}
printf("God please help our hero!\n");
printf("FINISH\n");
}
int main()
{
while(scanf("%d%d",&row,&col) != EOF)
{
t=0;
memset(flag,0,sizeof(flag));
for(int i = 0;i < row;i++)
scanf("%s",&a[i]);
bfs();
}
return 0;
}
