6044:鸣人和佐助

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms

内存限制: 

65536kB

描述

佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？

输入

输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。

输出

输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。

样例输入

样例输入14 4 1#@##**#####+****样例输入24 4 2#@##**#####+****

样例输出

样例输出16样例输出24

解题思路：

迷宫内求最少的时间，很明显的bfs或dp题型。数据量并不大。本蒟蒻本想在同学面前秀一下状压dp，结果仔细一看……老实用bfs吧。

这里比普通的二维迷宫加了一个时间，在不同的时间走到同一个格点，是不同的情况，扩展出来的新元素也会不同。所以我们需要在

标记数组中加一维用于记录时间。

如果你不用queue的话，最好自己写一个函数来模拟，尤其是这种用到结构体的bfs。否则会代码很凌乱。

注意一下p和t加1减1之类的，我这个代码应该不需要考虑了。

蒟蒻一只，有错误之处还请谅解。欢迎提问-.-

代码如下：

#include<cstdio>

#include<queue>

using namespace std;
char g[205][205];

int dic[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

int sx,sy,ex,ey;

int tmax,pmin;

int m,n;

bool b[205][205][15];

const int Inf=999999;
struct squ

{

	int x,y,p,t;

	squ(int xa,int ya,int pa,int ta):x(xa),y(ya),p(pa),t(ta){};//构造函数的一种类型：初始化列表。所以oop还是要学的

};

queue<squ> q;

void bfs()

{
//初始化

	int t=0,p=0,nx=0,ny=0;
	squ temp(sx,sy,0,tmax);

	q.push(temp);
while(!q.empty())

	{
//获取队首元素后弹出

		temp=q.front();

		t=temp.t;

		p=temp.p;

		if(temp.x==ex && temp.y==ey)

		{

			pmin=temp.p;

			return;

		}

		q.pop();
//四方向枚举

		for(int i=0;i<4;i++)

		{

			nx=temp.x+dic[i][0];

			ny=temp.y+dic[i][1];
			if(!b[nx][ny][t] && nx>0 && nx<=m && ny>0 && ny<=n && g[nx][ny] != '#' )

			{

				q.push(squ(nx,ny,p+1,t));

				b[nx][ny][t]=true;

			}
//由于C++运算符的短路现象，在&&中，当t>0不符合时，!b[nx][ny][t-1]不会执行，不必担心越界问题。

			if(t>0 && !b[nx][ny][t-1] && nx>0 && nx<=m && ny>0 && ny<=n && g[nx][ny] == '#')

			{

				q.push(squ(nx,ny,p+1,t-1));

				b[nx][ny][t-1]=true;

			}

		}

	}

}

int main()

{

	freopen("data.txt","r",stdin);//良好的调试习惯

	scanf("%d%d%d",&m,&n,&tmax);//尽量使用scanf和printf，这样更快。当然你要优化输入我。。。Orz

	pmin = Inf;

	getchar();

	for(int i = 1;i <= m;i++)

	{

		for(int j = 1;j <= n;j++)

		{

			scanf("%c",&g[i][j]);

			if(g[i][j] == '+')

			{

				ex = i;

				ey = j;

			}

			else if(g[i][j] == '@')

			{

				sx = i;

				sy = j;

			}

		}

		getchar();

	}

	if(sx==ex && sy == ey)

	{

		printf("0");

		return 0;

	}

	bfs();

	if(pmin==Inf)

		printf("-1");

	else

		printf("%d",pmin);

	return 0;

}