答案:<pre class="brush:cpp;toolbar:false">#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct POINT {
int x, y, tot;
bool get_jewel[7], enchantment;
} point, door;
int main() {
int k, F[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
scanf("%d", &k);
for (int kk = 1; kk <= k; kk++) {
queue<POINT> que;
int r, c, needkind, door_coord[15][2] = {}, sdoor_coord = 0;
char maze[205][205] = {};
bool walked[205][205][35] = {}, finish = false;
scanf("%d%d%d", &r, &c, &needkind);
for (int i = 0; i < r; i++) {
scanf("%s", maze[i]);
for (int j = 0; j < c; j++) {
if (maze[i][j] == 'S') {
memset(point.get_jewel, false, sizeof(point.get_jewel));
point.x = i;
point.y = j;
point.tot = 0;
point.enchantment = true;
}
if (maze[i][j] == '$') {
door_coord[sdoor_coord][0] = i;
door_coord[sdoor_coord++][1] = j;
}
}
}
que.push(point);
while (!que.empty()) {
for (int i = 0; i < 4; i++) {
point = que.front();
point.tot++;
point.x += F[i][0];
point.y += F[i][1];
if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
maze[point.x][point.y] == '#')
continue;
if ('0' <= maze[point.x][point.y] && maze[point.x][point.y] <= '4')
point.get_jewel[maze[point.x][point.y] - '0'] = true;
int sget_jewel = 0, ss = 0;
for (int i = 0; i < 5; i++)
if (point.get_jewel[i])
sget_jewel += pow(2, i), ss++;
if (walked[point.x][point.y][sget_jewel])
continue;
walked[point.x][point.y][sget_jewel] = true;
if (ss >= needkind)
point.enchantment = false;
if (maze[point.x][point.y] == '$') {
door = point;
for (int i = 0; i < sdoor_coord; i++)
if (door_coord[i][0] != point.x || door_coord[i][1] != point.y) {
door.x = door_coord[i][0];
door.y = door_coord[i][1];
que.push(door);
}
}
if (maze[point.x][point.y] == 'E' && !point.enchantment) {
printf("%d\n", point.tot);
finish = true;
}
if (finish)
break;
que.push(point);
}
if (finish)
break;
que.pop();
}
if (!finish)
printf("oop!\n");
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// 参考答案2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
int x, y, step, key;
node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
int cnt = 0;
for (int i = 0; i <= 5; i++)
if ((key >> i) & 1)
cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
if (cnt >= k)
return 1;
return 0;
}
int bfs(int x, int y) {
queue<node> que; // 根据结构体 定义队列que
dp[x][y][0] = 1;
node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
que.push(now); // 进队
while (!que.empty()) // 当队列不为空时 .empty()-->若队列为空返回1;
{
now = que.front(); // 把队头的值赋给now这个结构体上
que.pop(); // 弹出队首
for (int i = 0; i < 4; i++) // 上下左右四个执行方案
{
int xx = now.x + dir[0][i]; // 具体变动
int yy = now.y + dir[1][i];
int step = now.step; // 步数
int key = now.key; //
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
continue; // 判断边界
if (dp[xx][yy][key])
continue; // 若在队中 不走
if (map[xx][yy] == '#')
continue; // 禁区 不走
if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
{
return step + 1; // 返回步数 //结束遍历
}
if (isdigit(map[xx][yy])) //
{
dp[xx][yy][key] = 1; // 标记 相当于vis
key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
que.push(node(xx, yy, step + 1, key)); // 进队
}
if (map[xx][yy] == '.') // 普通地带
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key));
}
if (map[xx][yy] == '$') // 传送门
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
for (int j = 1; j <= tot; j++) // 遍历 方案
{
xx = trans[j][0], yy = trans[j][1];
if (!dp[xx][yy][key]) {
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
}
}
}
}
}
return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
cin >> T; // 组数
while (T--) {
memset(dp, 0, sizeof(dp));
tot = 0;
num = 0; // 初始化
scanf("%d%d%d", &n, &m, &k);
// cin>>n>>m>>k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> map[i][j];
// scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
// map[i][j]=getchar();
if (map[i][j] == 'S')
x = i, y = j, map[i][j] = '.'; // 标记起点
if (map[i][j] == '$')
trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
if (isdigit(map[i][j]))
num++; // 判断是否是宝石(数字)
}
if (k > num) {
printf("oop!\n");
continue;
} // 没有足够的宝石
ans = bfs(x, y);
if (ans == -1)
printf("oop!\n");
else
printf("%d\n", ans);
}
}</pre><pre class="brush:cpp;toolbar:false">// 参考答案3
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y, step; // 坐标 步长
bool germ[7], ench; // 找到的宝石 结界
} point, door;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int k;
int main() {
cin >> k;
while (k--) {
// 准备工作
queue<Point> q;
int r, c, needk; // 边界 需要宝石种类
cin >> r >> c >> needk;
int door_c[15][2]{}, door_n = 0; // 传送门坐标 数量
char ma[205][205]{}; // 地图
bool walked[205][205][35]{}, finish = false;
// 标记路是否走过及取得的宝石种类 是否完成
for (int i = 0; i < r; i++) {
cin >> ma[i];
for (int j = 0; j < c; j++) {
if (ma[i][j] == 'S') { // 起点
memset(point.germ, false, sizeof(point.germ));
point.x = i;
point.y = j;
point.step = 0;
point.ench = true;
}
if (ma[i][j] == '$') { // 传送门
door_c[door_n][0] = i;
door_c[door_n][1] = j;
door_n++;
}
}
}
// 广搜
q.push(point);
while (!q.empty()) {
for (int i = 0; i < 4; i++) {
point = q.front();
point.step++;
point.x += dx[i];
point.y += dy[i];
if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
(ma[point.x][point.y] == '#'))
continue;
if (ma[point.x][point.y] >= '0' &&
ma[point.x][point.y] <= '4') // 找到宝石
point.germ[ma[point.x][point.y] - '0'] = true;
int get_v = 0, s = 0;
for (int i = 0; i <= 4; i++) // 统计宝石
if (point.germ[i]) {
get_v += (int)pow(2, i);
s++;
}
if (walked[point.x][point.y][get_v])
continue; // 之前到达过
walked[point.x][point.y][get_v] = true; // 标记
if (s >= needk)
point.ench = false; // 结界消失
if (ma[point.x][point.y] == '$') { // 找到传送门
door = point;
for (int i = 0; i < door_n; i++) // 遍历所有的传送门
if ((door_c[i][0] != point.x) ||
(door_c[i][1] != point.y)) { // 可传送
door.x = door_c[i][0];
door.y = door_c[i][1];
q.push(door);
}
}
if (ma[point.x][point.y] == 'E' && !point.ench) { // 找到终点且无结界
cout << point.step << endl;
finish = true;
}
if (finish)
break;
q.push(point);
}
if (finish)
break;
q.pop();
}
if (!finish)
cout << "oop!" << endl;
}
return 0;
}</pre>
这道题暂未补解析。