T1215 拯救公主——bfs+三维数组标记+二进制状态压缩

分析

1. 此题和上题鸣人与佐助有点像，都是三维数组进行标记，因为比如说当前点传送过去走一格拿宝石后，然后再传送回来然后回终点，如果二维标记，拿完宝石就回不来了，所以说拿完宝石是一个新的状态；但是此题需要来标记宝石的数量
2. 在遍历过程中，每个地方有可能会走多次，举个例子：假如地图中一共有两种宝石（每个只有一个），而且这两个宝石都分别在一个胡同里（就是只有一条路能走进去相对应胡同取宝石），而且两个宝石还不在一个胡同里，走到终点时要求必须拿到这两个宝石。如果按正常的思路来（二维数组标记），每个地方只能走一次，当拿到一个宝石之后，就回不来了（因为走过的路被标记了，无法回来了），这样肯定解决不了这个问题了，所以就要用的三维数组标记来解决问题了。这里面一维和二维就是横坐标和纵坐标，三维用来存宝石的状态，按上面的例子来说，当一路走过去拿第一个宝石是，走的路肯定被标记了，但是标记的是没拿宝石路径，等拿到宝石之后，这时候状态又不一样了，这时候就能原路返回了（三维数组）。
3. 关于宝石的种类计数，刚开始采用数组标记每种宝石的出现情况进行累加，这样不知道为啥不对，后来看网上用的二进制状态压缩；最多五种宝石，用11111表示五种宝石，1的数量就是宝石种类数量。
   • (k>>i)&i 取出k二进制的第i位
   • k=k|1<<i,表示将tk的第i位赋为1
4. 此题细节：三维数组标记、二进制进行宝石种类统计（刚开始想的是visStone[10];//宝石的种类是否出现过，然后进行判断，是否累加1种新宝石，但是这样不对；），以及起点S可以再次走，要么访问他时，把它变成 ‘.’ ，要么在处理的时候，和 ‘.’ 一块处理；最后输出oop!不能用puts;
5. 不理解为啥我最后用puts(“oop!”);一直wa，最后突然发现cout<<“oop!”<<endl就过去了；

详细解析可参考：计蒜客-T1215-拯救公主—bfs+三维数组+二进制状态压缩----广搜进阶

#include<bits/stdc++.h>using namespace std;struct node {int x, y, time, kindCnt;
};const int N = 205;
char path[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
vector<pair<int, int>> v;//存放传送门
int vis[N][N][35];//第三维：当前坐标宝石种类的数量
//int visStone[10];//宝石的种类是否出现过
int t, r, c, k, flag;
queue<node> q;int check(int tk)//检查宝石的数量够不够
{int l = 0;for (int i = 0; i < 5; i++)if ((tk >> i) & 1)//位运算l++;if (l >= k)return 1;elsereturn 0;
}void bfs() {while (!q.empty()) {node current = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = current.x, y = current.y, time = current.time, kindCnt = current.kindCnt;//当前所在点int xx = x + dx[i];int yy = y + dy[i];if (!vis[xx][yy][kindCnt] && path[xx][yy] != '#' && xx >= 1 && yy >= 1 && xx <= r && yy <= c) {if (path[xx][yy] == '.' || path[xx][yy] == 'S') {//S也可以走，也可以在刚开始找起点时，赋值为‘.’node no;no.x = xx, no.y = yy, no.time = time + 1, no.kindCnt = kindCnt;vis[xx][yy][kindCnt] = 1;q.push(no);} else if (path[xx][yy] == '$') {vis[xx][yy][kindCnt] = 1;node no;no.x = xx, no.y = yy, no.time = time + 1, no.kindCnt = kindCnt;q.push(no);//传送门,把当前能传送的点全传送了for (int j = 0; j < v.size(); j++) {//不要用iif (!vis[v[j].first][v[j].second][kindCnt]) {//这里的time+1是x,y到xx,yy的时间，不是传送中消耗的时间no.x = v[j].first, no.y = v[j].second, no.time = time + 1, no.kindCnt = kindCnt;vis[v[j].first][v[j].second][kindCnt] = 1;q.push(no);}}} else if (path[xx][yy] >= '0' && path[xx][yy] <= '9') {//统计宝石//这种统计方法不对，不知道为啥/*int kind = path[xx][yy] - '0';if (!visStone[kind]) {visStone[kind] = 1;no.kindCnt = kindCnt + 1;}*/vis[xx][yy][kindCnt] = 1;kindCnt = kindCnt | (1 << (path[xx][yy] - '0'));//重点node no;no.x = xx, no.y = yy, no.time = time + 1, no.kindCnt = kindCnt;q.push(no);} else {if (check(kindCnt)) {//找到公主了cout << time + 1 << endl;flag = 1;return;}}}}}
}int main() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cin >> t;while (t--) {memset(vis, 0, sizeof vis);v.clear();//memset(visStone, 0, sizeof visStone);flag = 0;while (!q.empty())q.pop();cin >> r >> c >> k;int x, y;for (int i = 1; i <= r; ++i) {for (int j = 1; j <= c; ++j) {cin >> path[i][j];if (path[i][j] == 'S') {x = i, y = j;}if (path[i][j] == '$')v.push_back({i, j});}}node no;no.x = x, no.y = y, no.time = 0, no.kindCnt = 0;vis[x][y][0] = 1;//在(x,y)上时有0颗宝石时候已走过q.push(no);bfs();if (!flag)//puts("oop!");//用它一直wa，很不理解，导致调试代码一天了还没发现错cout << "oop!" << endl;}return 0;
}

一直WA(12/30)

puts(“oop!”);//用它一直wa，很不理解，导致调试代码一天了还没发现错
以及统计宝石，刚开始想的是visStone[10];//宝石的种类是否出现过，然后进行判断，是否累加1种新宝石，但是这样不对；