深度优先搜索 DFS

#include <bits/stdc++.h>
using namespace std;
int k, n, s1, s2, e1, e2, vis[105][105];
char maps[105][105];

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

bool dfs(int x, int y) {
	vis[x][y] = 1;
	int tx, ty;
	if (x == e1 && y == e2)
		return true;
	for (int i = 0; i < 4; i++) {
		tx = x + dx[i], ty = y + dy[i];
		if (tx >= 0 && tx < n && ty >= 0 && ty < n && maps[tx][ty] != '#' && vis[tx][ty] == 0)
			if (dfs(tx, ty))
				return true;
	}
	return false;
}

int main() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> n;
		for(int i=0;i<105;i++)
			for(int j=0;j<105;j++)
				vis[i][j]=0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				cin >> maps[i][j];
		cin >> s1 >> s2 >> e1 >> e2;
		if (dfs(s1, s2))
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}

广度优先搜索 BFS

#include <bits/stdc++.h>
using namespace std;
#define in cin
#define out cout
char maps[105][105];
int n, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1};
struct node {
	int x, y;
};
queue<node> q;
bool bfs(int sx, int sy, int ex, int ey) {
	while (!q.empty())
		q.pop();
	maps[sx][sy] = '#', q.push({sx, sy});
	while (!q.empty()) {
		int ux = q.front().x, uy = q.front().y;
		q.pop();
		if (ux == ex && uy == ey)
			return true;
		for (int i = 0; i < 4; i++) {
			int tx = dx[i] + ux, ty = uy + dy[i];
			if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] == '.')
				maps[tx][ty] = '#', q.push({tx, ty});
		}
	}
	return false;
}
int main() {
	int t;
	in >> t;
	while (t--) {
		in >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				in >> maps[i][j];
		int sx, sy, ex, ey;
		in >> sx >> sy >> ex >> ey;
		if (bfs(sx, sy, ex, ey))
			out << "YES\n";
		else
			out << "NO\n";
	}
	return 0;
}

动态规划 DP/图论 最短路-Floyd

#include <bits/stdc++.h>
using namespace std;
#define in cin
#define out cout
char maps[105][105];
int n, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1}, dp[105][105];

int main() {
	int t;
	in >> t;
	while (t--) {
		in >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				in >> maps[i][j];
		memset(dp, 0, sizeof(dp));
		int sx, sy, ex, ey;
		in >> sx >> sy >> ex >> ey;
		dp[sx][sy] = 1;
		for (int k = 0; k < n * n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (maps[i][j] == '.')
						for (int l = 0; l < 4; l++) {
							int tx = dx[l] + i, ty = dy[l] + j;
							if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] == '.')
								dp[i][j] = max(dp[i][j], dp[tx][ty]);
						}
		if (dp[ex][ey])
			out << "YES\n";
		else
			out << "NO\n";
	}
	return 0;
}