马上就要考 SCP 了，赶紧写一些题解积累人品

P3855 [TJOI2008]Binary Land 题解

很明显 可以看出这道题就是一个 BFS 的题目，利用 BFS 暴力搜到答案。

题目在讲什么

先输入行数 \(N\) 列数 \(M\)，再输入一个 \(N * M\) 的字符串矩阵

有 1 对情侣，他们的位置在矩阵中分别用 \(G\), \(M\) 表示。

他们的运动方式特别， 上下运动他们运动方向是一样的，左右运动则相反。

最后他们要在 \(T\) 点相遇，问最小的操作次数。

为什么BFS

• 用矩阵读入，在一张图上操作，一般方法是搜索。

• 标签里有。

• 求的是操作次数， 可见是一道 BFS 的模板题再多一点东西。

如何处理方向相反

大家都知道，在 BFS 的题中经常会用 2 个数组分别表示向 \(x\), \(y\) 方向的移动步数

由于这里是 2 个角色， 我们也要用 4 个数组来表示。

稍微一想就可以想到把数组 \(x\) 不变， \(y\) 相反即可

关于结构体

这很好想，有 2 个角色， 可以分别用 2 个 pair 模拟， 最后再来一个队列表示步数就可以了，他们都是同时进行的，故步数只用一个即可。

其中也可以用一个结构体解决，但我用的是前者。

关于 MLE

开始我的代码是这样的：

MLE代码

貌似没错，一交就基本全部 \(MLE\) 了。

MLE记录

经过检查发现没有用 \(VIS\) 数组， 当即开了一四维数组表示状态，结果直接就过了

代码如下：（不用云剪贴板了

#include <bits/stdc++.h>

using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
inline void print(int x){
	char P[105];int w=0;if(x==0){putchar('0');return;}
	if(x<0) putchar('-'),x=-x;
	while(x) P[++w]=x%10+'0',x/=10;
	for(int i=w; i>=1; i--) putchar(P[i]);
}
struct node {
	int x, y;
} One_start, Two_start;
queue<node> one, two;
queue<int> q;
const int N = 30;
const int dx[] = {0, 0, 1, -1},
		  dy[] = {1, -1, 0, 0},
		  Dx[] = {0, 0, 1, -1},
		  Dy[] = {-1, 1, 0, 0};
int n, m;
bool vis[40][40][40][40];
char ch[N + 1][N + 1];
inline bool  check(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m && ch[x][y] != 'X';
}
inline void bfs() {
	one.push(One_start), two.push(Two_start); q.push(0);
	while ("MLE") {
		if (one.empty()) break;
		if (two.empty()) break;
		if (q.empty()) break;
		int cnt = q.front(); q.pop();
		node o = one.front(), t = two.front();one.pop();two.pop();
		if (vis[o.x][o.y][t.x][t.y]) continue;
		vis[o.x][o.y][t.x][t.y] ^= 1;
		if (o.x == t.x && o.y == t.y && ch[o.x][o.y] == 'T') {
			print(cnt);
			exit(0);
		}
		for (int i = 0; i < 4; i++) {
			int x = dx[i] + o.x, y = dy[i] + o.y,
				X = Dx[i] + t.x, Y = Dy[i] + t.y;
			if (check(x, y) && check(X, Y)) {
				if (ch[x][y] == '#') 
					one.push({o.x, o.y});
				else 
					one.push({x, y});
				if (ch[X][Y] == '#') 
					two.push({t.x, t.y});
				else 
					two.push({X, Y});
				q.push(cnt + 1);
			}
		}
	}
}
int main () {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> ch[i][j];
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
		if (ch[i][j] == 'G') One_start = {i, j};
		if (ch[i][j] == 'M') Two_start = {i, j};
	}
	bfs();
	puts("no");
	return 0;
}