A45686. Project Summer 游戏小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏， 小 I 扮演这个游戏中需要逃生的无辜者（Innocent)， 小 B 扮演这个游戏中抓住无辜者， 阻止其逃生的背叛者（Betrayer）。这个游戏的地图是一个 N 行 M 列 的矩形， 每个格点表示一个位置。'#' 表示地图中的障碍物， '.' 表示地图中的空地， 此外， 地图中还有只…
题目描述
Project Summer 游戏
小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏， 小 I 扮演这个游戏中需要逃生的无辜者（Innocent)， 小 B 扮演这个游戏中抓住无辜者， 阻止其逃生的背叛者（Betrayer）。这个游戏的地图是一个 N 行 M 列 的矩形， 每个格点表示一个位置。'#' 表示地图中的障碍物， '.' 表示地图中的空地， 此外， 地图中还有只有背叛者才能使用的传送门， 用小写字母 'a' - 'z' 标记， 它们在地图上成对出现。角色可以花费 1 单位的时间从一个格子走到上下左右相邻的 4个空地中的另一个格子（不可以走出地图边界或者走到障碍物上）。此外， 当小 B 扮演的背叛者走到一个传送门上时， 他可以花费 1 单位的时间从当前格子传送到与当前格子相同字母的另一个传送门处（他也可以选择不传送， 此时没有花费任何时间， 待在原地不动）。传送是双向的。 比如， 现在小 B 走到了标记为 'a' 的格子上， 那么他可以选择花费一单位的时间传送到另一个标记为 'a' 的格子上， 也可以选择不传送， 那么他就待在原地不动。现在， 小 I 被小 B 的陷阱困住了， 无法移动。 给出地图上小 B 和小 I 所在的格子（他们都站在空地上）， 求小 B 最少需要花费多少时间才能走到小 I 所在的格子抓住他。 如果小 I 无法抓住小 B， 输出 -1
输入
第一行一个数字 T, 表示数据组数。 接下来描述 T 组数据， 每组数据最开始是两个正整数 N, M 表示地图是 N 行 M 列的矩形。 接下来 N 行， 每行 M 个字符， 表示地图。 在地图上， 用 '.' 表示空地，'#' 表示障碍物， 'a'-'z' 表示传送门， 'B' 表示小 B 的初始位置， 'I' 表示小 I 的初始位置。 对于每组数据， 保证在地图上标记相同的传送门恰好出现两次。 T,N,M <= 100
输出
T 行， 第 i 行输出 'Case #i: t', 表示第 i 组数据的答案是 t. 小 B 最少需要 t 单位时间才能走到小 I 所在的格子。 如果小 I 无法抓住小B， 输出 -1
样例输入
3
5 5
Bx#..
#a.#.
.....
##..#
.x.aI
5 5
BIa.a
x#.x.
.#.##
.....
#####
2 2
B#
#I
样例输出
Case #1: 4
Case #2: 1
Case #3: -1
参考答案
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int T, N, M;
int ii, jj;
int directs[4][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[100][100];
int visited[100][100];
struct Data {
int i, j, t;
Data(int _i, int _j, int _t) : i(_i), j(_j), t(_t) {}
};
Data gogogo(const Data &d) {
char c = a[d.i][d.j];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (a[i][j] == c && !(d.i == i && d.j == j)) {
return Data(i, j, d.t + 1);
}
}
}
return d;
}
int main() {
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> a[i][j];
if (a[i][j] == 'B') {
ii = i;
jj = j;
}
}
}
queue<Data> q;
memset(visited, -1, sizeof(visited));
q.push(Data(ii, jj, 0));
visited[ii][jj] = 0;
bool flag = 0;
while (!q.empty()) {
Data cur = q.front();
if (a[cur.i][cur.j] == 'I') {
flag = 1;
break;
}
q.pop();
int ni, nj, nt;
for (int d = 0; d < 4; ++d) {
ni = cur.i + directs[d][0];
nj = cur.j + directs[d][1];
nt = cur.t + 1;
if (ni >= 0 && ni < N && nj < M && nj >= 0 && a[ni][nj] != '#' &&
(visited[ni][nj] == -1 || nt < visited[ni][nj])) {
visited[ni][nj] = nt;
q.push(Data(ni, nj, nt));
}
}
// 气！isalpha函数在OJ上会被判错
if (a[cur.i][cur.j] <= 'z' && a[cur.i][cur.j] >= 'a') {
Data nd = gogogo(cur);
if (visited[nd.i][nd.j] == -1 || nd.t < visited[nd.i][nd.j]) {
visited[nd.i][nd.j] = nd.t;
q.push(nd);
}
}
}
cout << "Case #" << t << ": " << ((flag) ? q.front().t : -1) << endl;
}
}