题解 | 迷宫

用dfs解的，其实就是S所在的块的最大最小行和最大最小列和E所在块的最大最小行和最大最小列的范围中

#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int, int>> min_max_row(2,{0x3f3f3f3f,0}); //min,max
vector<pair<int, int>> min_max_column(2,{ 0x3f3f3f3f,0 }); //min,max
pair<int, int> start;
pair<int, int> the_end;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

bool visited[1001][1001];

bool check(vector<vector<char>>& graph, int x, int y) {
	if (x < n && y < m && x >= 0 && y >= 0 &&!visited[x][y] && graph[x][y] == '.') {
		return true;
	}
	return false;
}

void dfs(vector<vector<char>> &graph , int x,int y,int index) {
	visited[x][y] = true;
	min_max_column[index].first = min(min_max_column[index].first, x);
	min_max_column[index].second = max(min_max_column[index].second, x);
	min_max_row[index].first = min(min_max_row[index].first, y);
	min_max_row[index].second = max(min_max_row[index].second, y);
	for (int k = 0; k < 4; k++) {
		if (check(graph, x + dx[k], y + dy[k])) {
			dfs(graph, x + dx[k], y + dy[k],index);
		}
	}
}

int main() {

	cin >> n >> m;
	vector<vector<char>> graph(n, vector<char>(m));
	for (int k = 0; k < n; k++) {
		for (int j = 0; j < m; j++) {
			cin >> graph[k][j];
			if (graph[k][j] == 'S') {
				start = { k,j };
				graph[k][j] = '.';
			}
			if (graph[k][j] == 'E') {
				the_end = { k,j };
				graph[k][j] = '.';
			}
		}
	}
	dfs(graph, start.first, start.second, 0);
	memset(visited, false, sizeof(visited));
	dfs(graph, the_end.first, the_end.second, 1);
	if (min_max_row[0].first <= min_max_row[1].second + 1 && min_max_row[0].second >= min_max_row[1].first - 1) {
		cout << "YES";
		return 0;
	}
	if (min_max_column[0].first <= min_max_column[1].second + 1 && min_max_column[0].second >= min_max_column[1].first - 1) {
		cout << "YES";
		return 0;
	}
	cout << "NO";
	return 0;

}