计蒜客题解

计蒜客题解

题目概况

链接：
难度： 普及/提高-（计蒜客评价普及T3）

题目分析

简化题目： 一张地图中，起点是S，终点是E，有禁区#、传送门$、宝石0-4，安全区 . 这些地方，求拿着K种宝石到达E的最短时间，到不了就输出“oop！”
涉及知识点: 广度优先搜索BFS、二进制状态压缩、位运算
解题思路：
通过BFS，逐情况讨论状态即可，状态便是 (tx, ty, tk, tdis) tx，ty表示坐标，tk表示当前宝石数，tdis表示当前步数。但我们的宝石需要用二进制表示压缩空间（11111就是五种宝石的状态，1的数量就是宝石的种数），要不然–boom！代码实现细节较多，难度较大

代码要点拆解

一、数据准备

struct node {int x, y, k, dis;node(int _x, int _y, int _k, int _dis) { //结构体构造函数x = _x;y = _y;k = _k; //当前宝石数（二进制状压）dis = _dis; //步数}
};
const int MAXN = 205;
int T; //数据组数
int t; //统计传送门数量
int R, C; //地图大小
int K; //要求的K种宝石
int vis[MAXN][MAXN][MAXN]; //标记走过的地方
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //移动坐标
int door[15][15]; //传送门坐标
char maze[MAXN][MAXN]; //地图存储
queue <node> q; //bfs用的好东西

二、主函数内的玄学 操作

要点一览：
1. 在使用前清空不能继续用的数据
2. 输入地图，同时记录起点、传送门
3. 开始BFS记录答案
然后再看注释理解。

int main() {cin >> T;while (T--) {//清空部分数据t = 0; //传送门是必须清空的，但ans由于每次都会重新计算赋值，也就没必要清空了memset(vis, 0, sizeof(vis)); //一函清零真香while (!q.empty()) {q.pop();} //清空队列的操作（真麻烦）int startx, starty; //起点cin >> R >> C >> K;for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {cin >> maze[i][j]; if (maze[i][j] == 'S') {startx = i;starty = j; //记录}if (maze[i][j] == '$') {door[t][0] = i; //记录传送门door[t][1] = j;t++; }}}int ans = bfs(startx, starty); //开始核心操作if (ans == -1) { //如果没救了cout << "oop!" << endl;} else {cout << ans << endl;}}return 0;
}

三、BFS中的特殊情况考虑

私以为的一个点可以让BFScontinue或者直接return，不需要继续求状态的就是特殊情况：
1. 不在范围内的
2. 已经访问过的
3. 该点是禁区的
4. 该点是终点的（记得判断一下到终点了宝石够不够）

         if (!in(tx, ty)) { //如果不在范围内continue;}if (vis[tx][ty][tk]) {continue;}if (maze[tx][ty] == '#') {continue;}if (maze[tx][ty] == 'E') {if (check(tk)) { //判断宝石够不够return tdis + 1; //到终点还得走一步} }

四、BFS中的一般情况的状态处理

1.安全区

安全区直接把步数加1即可

if (maze[tx][ty] == '.') {vis[tx][ty][tk] = true;q.push(node(tx, ty, tk, tdis + 1));}

2.传送门

题面中说过：“当然蒜头君也可以选择不通过传送门瞬移”。
所以我们分情况考虑用传送门和不用传送门两种情况
细节问题见注释。

if (maze[tx][ty] == '$') {vis[tx][ty][tk] = true; q.push(node(tx, ty, tk, tdis + 1)); //如果不用这个传送门的状态for (int j = 0; j < t; j++) { //传送门有t个if (!vis[door[j][0]][door[j][1]][tk]) { //传送记得检查一下来过没，不能重复vis[door[j][0]][door[j][1]][tk] = true; q.push(node(door[j][0], door[j][1], tk, tdis + 1)); //各位一定记住这个传送的状态中要写door[j][0]和door[j][1],千万别写tx和ty！！！！//（我才不会告诉你我因为这个30组只对3组呢） }}}

3.捡宝石（难点）

位运算相关：.html
tk = tk|(1 << x) 表示向tk的第x位赋值1

         if (maze[tx][ty] >= '0' && maze[tx][ty] <= '9') {vis[tx][ty][tk] = true;tk = tk|(1 << (maze[tx][ty] - '0'));q.push(node(tx, ty, tk, tdis + 1));}

五、宝石检查函数（难点）

(x >> i) & 1表示判断x的第i位是否为1

bool check(int x) { //检查宝石数量够不够int l = 0; //统计有几个1，几个1就有几种宝石在手上for (int i = 0; i < 5; i++) { //5位转一遍if ((x >> i)&1) {l++;}}if (l >= K) {return true;}return false;
}

最后还有个in函数，用来判断是否在地图范围内的，我想在座各位应该都会，就不写了

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;//起点是蒜头君S，终点是公主E，有禁区#、转送门$、宝石0-4（要集齐K种），安全区.
struct node {int x, y, k, dis;node(int _x, int _y, int _k, int _dis) {x = _x;y = _y;k = _k; //当前宝石数（二进制状压）dis = _dis; //步数}
};
const int MAXN = 205;
int T; //数据组数
int t;
int R, C; //地图大小
int K; //要集齐K种宝石
int vis[MAXN][MAXN][MAXN]; //记录走过没
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int door[15][15];
char maze[MAXN][MAXN];
queue <node> q;bool in(int a, int b) {return a >= 1 && a <= R && b >= 1&& b <= C;
}bool check(int x) { //检查宝石数量够不够int l = 0;for (int i = 0; i < 5; i++) {if ((x >> i)&1) {l++;}}if (l >= K) {return true;}return false;
}int bfs(int xx, int yy) {node now(xx, yy, 0, 0);q.push(now);vis[xx][yy][0] = true;while (!q.empty()) {now = q.front();q.pop();for (int i = 0; i < 4; i++) {int tx = now.x + dir[i][0];int ty = now.y + dir[i][1];int tk = now.k;int tdis = now.dis;if (!in(tx, ty)) { //如果不在范围内continue;}if (vis[tx][ty][tk]) {continue;}if (maze[tx][ty] == '#') {continue;}if (maze[tx][ty] == 'E') {if (check(tk)) {return tdis + 1;} }if (maze[tx][ty] == '.') {vis[tx][ty][tk] = true;q.push(node(tx, ty, tk, tdis + 1));}if (maze[tx][ty] == '$') {vis[tx][ty][tk] = true;q.push(node(tx, ty, tk, tdis + 1)); //如果不用这个传送门for (int j = 0; j < t; j++) {if (!vis[door[j][0]][door[j][1]][tk]) {vis[door[j][0]][door[j][1]][tk] = true;q.push(node(door[j][0], door[j][1], tk, tdis + 1)); }}}if (maze[tx][ty] >= '0' && maze[tx][ty] <= '9') {vis[tx][ty][tk] = true;tk = tk|(1 << (maze[tx][ty] - '0'));q.push(node(tx, ty, tk, tdis + 1));}}}return -1;
}int main() {cin >> T;while (T--) {//清空部分数据t = 0;memset(vis, 0, sizeof(vis));while (!q.empty()) {q.pop();}int startx, starty;cin >> R >> C >> K;for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {cin >> maze[i][j];if (maze[i][j] == 'S') {startx = i;starty = j;}if (maze[i][j] == '$') {door[t][0] = i; //记录传送门door[t][1] = j;t++;}}}int ans = bfs(startx, starty);if (ans == -1) {cout << "oop!" << endl;} else {cout << ans << endl;}}return 0;
}