从今以后,我将会用一个假的标题!
当然,不是每天都是愚人节(
传送门
???
思路
状压+爆搜。
状压——压机关的触发。
比如:11010 B
就表示第 2 、第 4 、第 5 个机关被触发了奇数次。
当我们踏上一个新格子时:
- 检查这个格子被影响了多少遍,以及这个格子最初能不能走,以此来判断这是不是墙。
- 检查这个状态有没有走过。
- 切换状态。
注意: - 要记录 $ r, c, dist, state $ 四个属性。
- 不要把 $ dist $ 存到数组里,会爆空间啊!!!
代码
#include <bits/stdc++.h>
using namespace std;
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int n, m, k;
bool vis[1 << 15][35][35];
bool maze[35][35];
int r[15], c[15], R[15], C[15];
int sr, sc, tr, tc;
queue<pair<pair<int, int>, pair<int, int> > > que;
void get_maze() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
getchar();
getchar();
for (int j = 0; j < m; j++) {
char ch = getchar();
if (ch == 'S') {
sr = i, sc = j;
} else if (ch == 'T') {
tr = i, tc = j;
} else if (ch == '#') {
maze[i][j] = 1;
}
}
}
}
void get_button() {
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d %d %d %d", &r[i], &c[i], &R[i], &C[i]);
r[i]--;
c[i]--;
R[i]--;
C[i]--;
}
}
bool changed_time(int rr, int cc, int state) {
bool ans = 0;
for (int i = 0; i < k; i++) {
if ((state >> i) & 1) {
if (R[i] == rr && C[i] == cc) {
ans = !ans;
}
}
}
return ans;
}
int change(int st, int rr, int cc) {
for (int i = 0; i < k; i++) {
if (r[i] == rr && c[i] == cc) {
st ^= (1 << i);
}
}
return st;
}
void bfs() {
que.push(make_pair(make_pair(0, 0), make_pair(sr, sc)));
vis[0][sr][sc] = 1;
while (que.size()) {
int st = que.front().first.first;
int dis = que.front().first.second;
int cr = que.front().second.first;
int cc = que.front().second.second;
if (cr == tr && cc == tc) {
printf("%d", dis);
break;
}
que.pop();
for (int i = 0; i < 4; i++) {
int nr = cr + dr[i];
int nc = cc + dc[i];
if (!(0 <= nr && nr < n && 0 <= nc && nc < m)) {
continue;
}
if (!changed_time(nr, nc, st) ^ maze[nr][nc] && !vis[change(st, nr, nc)][nr][nc]) {
vis[change(st, nr, nc)][nr][nc] = 1;
que.push(make_pair(make_pair(change(st, nr, nc), dis + 1), make_pair(nr, nc)));
}
}
}
}
int main() {
get_maze();
get_button();
bfs();
return 0;
}
感觉我现在就是水博客/kk
标签:ch,rr,int,谜题,++,P3869,ans,cc,机关 From: https://www.cnblogs.com/AProblemSolver/p/16926505.html