Problem J

僵尸来了

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

僵尸要来佳佳家做客了，佳佳把花园布置了一下，你拿到了花园的地图（以二维矩阵的形式表示）以及起点和佳佳家的位置。花园里某些位置有地刺，僵尸过的时候每次需要消耗一个单位的生命值，僵尸有一定数量的生命值，看看最聪明的僵尸能否在天亮前到达你的家里？能的话，最少花费多少时间。

输入：

输入的第一行包含三个整数：m，n，t。代表m行n列的地图和僵尸的生命值t。m,n都是小于200的正整数，t是小于10的正整数，第2行开始的m行是m行n列的花园地图，其中!代表起点，+表示佳佳家。*代表通路，w代表地刺。

输出：

输出僵尸到达佳佳家最少需要花费的时间。如果无法到达，则输出-1。

输入样例：

4 4 2
w!ww
**ww
www+
****

输出样例：

6

#include <iostream>
#include <queue>
using namespace std;

struct rec {
	int x, y;//僵尸当前坐标
	bool useful;//该状态是否有效
	int t;//僵尸当前生命值
	int step;//僵尸当前步数
};
queue<rec> q;
rec st, ed;
char maze[201][201];//地图
int visited[201][201][10];
int m, n, t;

int dx[4] = {0, 0, -1, 1};//左右上下四个方向
int dy[4] = {-1, 1, 0, 0};

void init() {
	cin >> m >> n >> t;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
			if (maze[i][j] == '!') {//僵尸出发点
				st.x = i, st.y = j;
			}
			if (maze[i][j] == '+') {//目标位置
				ed.x = i, ed.y = j;
			}
		}
	}
	st.t = t;
	st.step = 0;
}

rec moveto(rec now, int i) {
	rec next;
	next.x = now.x + dx[i];
	next.y = now.y + dy[i];
	if (next.x < 0 || next.x >= m || next.y < 0 || next.y >= n) {
		next.useful = false;
		return next;
	}
	if (maze[next.x][next.y] == 'w') {//如果遇到地刺
		next.t = now.t - 1;
	} else if (maze[next.x][next.y] != 'w') {//如果遇到非地刺
		next.t = now.t;
	}
	if (next.t <= 0) {//僵尸体力值为0， 僵尸死亡
		next.useful = false;
		return next;
	}
	next.useful = true;
	return next;

}

int bfs() {
	q.push(st);
	while (q.size()) {
		rec now = q.front();
		if (now.x == ed.x && now.y == ed.y) {//到达目标
			return now.step;//返回最小步数
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			rec next = moveto(now, i);
			if (next.useful == true && !visited[next.x][next.y][next.t]) {
				visited[next.x][next.y][next.t] = 1;
				next.step = now.step + 1;
				q.push(next);
			}
		}
	}
	return -1;//不能到达
}

int main() {
	init();
	int ans = bfs();
	cout << ans << endl;
	return 0;
}