百练 - 4115 火影忍者与佐助

最近发现太久没碰的知识点居然手生了，所以决定复习一波之前写过的题，结果还发现之前是写错的，真有意思...

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

输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
输出
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。

样例输入1

样例输入2

样例输出1
6

样例输出2
4

解析：这道题用dfs好像怎么搞都会T掉，那么就bfs。不过这道题比较坑，还多了一个查克拉数量，那么也就是说，假如之前走过某个点，其实下次还可以走，因为假如每个点只能走一次，那可能会出现原本可以走通，但却没能走通的情况，因为这可能还取决于查克拉的数量，在传统的迷宫问题上多加了一个条件。其次是假如'#'，那么查克拉的数量必须大于0，否则走不过去。
这里假如分两种情况：

1. 遇到'#'
2. 遇到！'#'

我一开始是写遇到''，因为'+'既非''也非'#'，所以会永远走不到，不过可以把'+'换成'*'也可以。
然后我还发现好像这个数据的时间可能还能达到1e9嘛，没搞懂这个评测机居然初始化minT为inf，然后用minT和inf作比较居然过不了，我人都傻掉。

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod =1e9 + 7;
int map[205][205], vis[205][205][15];
int minT = 0, m, n, k;
int dir[4][2] = {{1,0}, {0, 1}, {-1, 0}, {0, -1}};
int r1, l1, r2, l2;
struct node
{
	int x, y, t, k; //横坐标, 纵坐标, 时间, 查克拉数量 
}; 
queue<struct node>q;
bool cp(int xx, int yy)
{
	if(xx < 1 || yy < 1 || xx > m || yy > n)
		return 0;
	else
		return 1;
}

int bfs()
{
	node temp, point, nowP;
	vis[r1][l1][k] = 1;
	temp.x = r1, temp.y = l1, temp.t = 0, temp.k = k;
	q.push(temp);
	while(q.size())
	{
		point = q.front();
		q.pop();
		if(point.x == r2 && point.y == l2)
			return point.t;
		for(int i = 0; i < 4; i++)
		{
			int xx = point.x + dir[i][0];
			int yy = point.y + dir[i][1];
			if(cp(xx, yy) && map[xx][yy] == '#' && !vis[xx][yy][point.k - 1] && point.k >= 1)
			{
				vis[xx][yy][point.k - 1] = 1;
				nowP.x = xx, nowP.y = yy, nowP.t = point.t + 1, nowP.k = point.k - 1;
				q.push(nowP);
			}
			else if(cp(xx, yy) && map[xx][yy] != '#' && !vis[xx][yy][point.k]) //如果是map[xx][yy] == '*',会无法到达'+' 
			{
				vis[xx][yy][point.k] = 1;
				nowP.x = xx, nowP.y = yy, nowP.t = point.t + 1, nowP.k = point.k;
				q.push(nowP);
			}
		} 
	}
}

int main()
{
	scanf("%d%d%d", &m, &n, &k);
	getchar();
	for(int i = 1; i <= m; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			scanf("%c", &map[i][j]);
			 if(map[i][j] == '@')
			     r1 = i, l1 = j;
			 else if(map[i][j] == '+')
			 	 r2 = i, l2 = j;
		}
		getchar();
	}
	memset(vis, 0, sizeof(vis));
	minT = bfs();
	if(minT)
		printf("%d\n", minT);
	else
		printf("-1\n");
	return 0;
}