- 迷宫
急需题解!
- 2025-3-30 16:54:21 @
P2499 迷宫 😕
1 comments
-
陈国瑞 LV 10 @ 2025-6-22 1:14:29Edited
深度优先搜索 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; }
- 1
Information
- ID
- 2499
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 133
- Accepted
- 14
- Uploaded By