O - 胜利大逃亡(续)

---

题目分析 

        bfs+状态压缩（在bfs的基础上，存储持有不同钥匙时，此点位是否走过的情况）；

-----状态压缩使用二进制实现，同时通过位运算修改是否转移至另一状态（详情见代码及注释）

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 35;struct demo{int x, y, val, key; //key用于存储钥匙情况
}st;int n, m, t;
char g[N][N];int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int bfs()
{bitset<1<<11> vis[N][N];// 1左移11位以分别存储11把钥匙的持有情况//0未持有，1持有vis[st.x][st.y][st.key] = 1;queue<demo> q;q.push(st);demo next, now;while(!q.empty()){now = q.front(); q.pop();for(int i = 0; i < 4; i++){next.x = now.x + dx[i]; next.y = now.y + dy[i];next.val = now.val + 1; next.key = now.key;if(next.x < 1 || next.y < 1 || next.x > n || next.y > m) continue;if(vis[next.x][next.y][next.key] || g[next.x][next.y] == '*') continue; //如果当前要进入的点在如今的状态走过，则跳过vis[next.x][next.y][next.key] = 1;if(next.val >= t) return -1;if(g[next.x][next.y] == '^') return next.val;if(g[next.x][next.y] >= 'A' && g[next.x][next.y] <= 'J'){int temp = g[next.x][next.y] - 'A';if(next.key & (1 << temp)) q.push(next);continue;}if(g[next.x][next.y] >= 'a' && g[next.x][next.y] <= 'j'){int temp = g[next.x][next.y] - 'a';next.key |= (1 << temp); //更新钥匙持有情况}q.push(next);}}return -1;
}int main()
{ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);while(cin >> n >> m >> t){for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> g[i][j];if(g[i][j] == '@'){st.x = i; st.y = j; st.val = st.key = 0;}}}cout << bfs() << '\n';}return 0;
}

---

 S - Key Task

---

题目分析 

        一样是bfs+状态压缩,但需要对数据进行处理，bitset开不下

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 120;struct demo{int x, y, val, key;
}st;int r, c;
char g[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};int bfs(){bitset<1 << 5> vis[N][N];demo next, now;queue<demo> q;vis[st.x][st.y][st.key] = 1;q.push(st);while(!q.empty()){now = q.front(); q.pop();for(int i = 0; i < 4; i++){next.x = now.x + dx[i]; next.y = now.y + dy[i];next.val = now.val + 1; next.key = now.key;if(next.x < 1 || next.y < 1 || next.x > r || next.y > c) continue;if(vis[next.x][next.y][next.key] || g[next.x][next.y] == '#') continue;vis[next.x][next.y][next.key] = 1;if(g[next.x][next.y] == 'X') return next.val;if(g[next.x][next.y] >= 'A' && g[next.x][next.y] <= 'Z'){int k;if(g[next.x][next.y] == 'B') k = 0;else if(g[next.x][next.y] == 'Y') k = 1;else if(g[next.x][next.y] == 'R') k = 2;else if(g[next.x][next.y] == 'G') k = 3;if(next.key & (1 << k))  q.push(next);continue;}if(g[next.x][next.y] >= 'a' && g[next.x][next.y] <= 'z'){int k;if(g[next.x][next.y] == 'b') k = 0;else if(g[next.x][next.y] == 'y') k = 1;else if(g[next.x][next.y] == 'r') k = 2;else if(g[next.x][next.y] == 'g') k = 3;next.key |= (1 << k);}q.push(next);}}return -1;
}int main()
{ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);while(cin >> r >> c){int ans = 0;if(r == 0 && c == 0) return 0;for(int i = 1; i <= r; i++){for(int j = 1; j <= c; j++){cin >> g[i][j];if(g[i][j] == '*'){st.x = i; st.y = j; st.val = st.key = 0;}}}ans = bfs();if(ans == -1) cout << "The poor student is trapped!" << '\n';else cout << "Escape possible in " << ans << " steps." << '\n';}return 0;
}

---

        状态压缩适用于存在大量状态的问题，进而实现将多个状态存于一个整数中

---

 B - Fliptile

 

---

题目分析 

        1.多次反转无意义，奇数次的反转等效1次反转；偶数次相当于不反转；

        2.对于当前行黑色块，可以通过对下一行相同位置反转进而实现当前行整体颜色反转

        3.可以通过二进制枚举暴力枚举出第一行所有翻转情况，进而逐步推导下一行翻转情况；

而若到最后一行时仍有黑色块存在，则说明该枚举情况不可行；

---

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 20;int m, n;
int ans = 1e7;
int st[N][N];   //起始图例
int turn[N][N]; //翻转图例
int ed[N][N];   //答案图例
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int solve()
{int now[N][N];memcpy(now, st, sizeof st);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(i != 1 && now[i - 1][j] == 1) turn[i][j] = 1;if(turn[i][j]){now[i][j] ^= 1;for(int k = 0; k < 4; k++){int a = i + dx[k], b = j + dy[k];now[a][b] ^= 1;}}}}for(int j = 1; j <= n; j++) if(now[m][j]) return -1;int temp = 0;for(int i  = 1; i <= m; i++)for(int j = 1; j <= n; j++) temp += now[i][j];return temp;
}int main()
{cin >> m >> n;int flag = 0;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++) cin >> st[i][j];//二进制枚举所有情况for(int i = 0; i < (1 << n); i++){memset(turn, 0, sizeof turn);for(int j = 0; j < n; j++){if (i & (1 << j)) turn[1][j + 1] = 1;}int temp = solve();if(temp != -1){flag = 1;if(temp < ans){memcpy(ed, turn, sizeof turn);ans = temp;}}}if(!flag) cout << "IMPOSSIBLE" << '\n';else{for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++) cout << ed[i][j] << ' ';cout << '\n';}}return 0;
}

---