OpenJudge 原题

蒟蒻的 bfs 一直是 MLE，但是我找不到问题……

dfs 过了，看起来区别不很大，为什么 bfs 爆栈捏？

求分析：

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 101;
int T, n, ha, la, hb, lb,
	fx[5] = {0, -1, 1, 0, 0}, // 四个方向
	fy[5] = {0, 0, 0, -1, 1};
char a[INF][INF]; // 读入的数组
queue < pair <int, int> > Q; // 队列

bool check(int xx, int yy){ // 检查越界
	return xx >= 0 && xx < n && yy >= 0 && yy < n;
}

int main(){
	ios :: sync_with_stdio(false);

	cin >> T;
	while(T--){
		cin >> n;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> a[i][j];
			}
		}
		cin >> ha >> la >> hb >> lb;
		while(!Q.empty()) Q.pop(); // 清空队列
		Q.push({ha, la}); // 初始化
		bool flag = false; // 标记是否有解
		if(a[ha][la] == '.' && a[hb][lb] == '.') // 起点和终点都能走
			while(!Q.empty()){
				auto fr = Q.front(); Q.pop();
				int x = fr.first, y = fr.second;
				a[x][y] = '#'; // 标记走过了
				if(x == hb && y == lb){ // 到达终点
					flag = true;
					break;
				}
				for(int i = 1; i <= 4; i++){ // 四个方向搜索
					int xx = x + fx[i], yy = y + fy[i];
					if(check(xx, yy) && a[xx][yy] == '.'){ // push 进队列
						Q.push({xx, yy});
					}
				}
			}
		if(flag) cout << "YES\n"; // 输出
		else cout << "NO\n";
	}

	return 0;
}