从今以后，我将会用一个假的标题！
当然，不是每天都是愚人节（

传送门

？？？

思路

状压+爆搜。
状压——压机关的触发。
比如：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

原文地址：http://www.cnblogs.com/AProblemSolver/p/16926505.html