答案:<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>
这道题暂未补解析。