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;
}