BFS Algorithm TODO: 记录路径的方式有待优化
#pragma GCC optimize(2)// 吸口氧气
#pragma GCC optimize(3)// 吸口臭氧
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
static constexpr int dirs[] {0, -1, 0, 1, 0};
using namespace std;
using P = pair<int, int>;
const int N = 1010;
int g[N][N], n;
int main() {
scanf("%d", &n);
map<P, P> paths;
paths[{0, 0}] = {-1, -1};
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x) cin >> g[y][x];
queue<P> q;
q.emplace(0, 0);
g[0][0] = 1; // mark as visited
while (not q.empty()) {
const auto [x, y] = q.front(); q.pop();
if (x == n - 1 && y == n - 1) {
P cur{n - 1, n - 1}, dummy{-1, -1};
vector<P> ans;
while (cur != dummy) {
ans.emplace_back(cur);
cur = paths[cur];
}
reverse(begin(ans), end(ans));
for (int i = 0; i < ans.size(); ++i)
printf("%d %d\n", ans[i].second, ans[i].first);
return 0;
}
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == n || ny == n || g[ny][nx] == 1)
continue;
paths[{nx, ny}] = {x, y};
q.emplace(nx, ny);
g[ny][nx] = 1;
}
}
return 0;
}
相同的算法。但优化了路径记录方式(HashTable果真是性能杀手!)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using P = pair<int, int>;
static constexpr int dirs[] {0, -1, 0, 1, 0};
int n;
void bfs(vector<vector<int>>& g, vector<vector<P>>& parents) {
queue<P> q;
q.emplace(0, 0);
g[0][0] = 1;
while (not q.empty()) {
const auto [x, y] = q.front(); q.pop();
if (x == n - 1 && y == n - 1) return;
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == n || ny == n || g[ny][nx])
continue;
q.emplace(nx, ny);
g[ny][nx] = 1;
parents[ny][nx] = {y, x};
}
}
}
int main(void) {
cin >> n;
vector<vector<int>> g(n, vector<int>(n));
vector<vector<P>> parents(n, vector<P>(n));
parents[0][0] = {-1, -1};
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x) cin >> g[y][x];
bfs(g, parents);
P p = {n - 1, n - 1};
vector<P> ans;
while (p != P{-1, -1}) {
ans.emplace_back(p);
p = parents[p.first][p.second];
}
reverse(begin(ans), end(ans));
for (const auto& [y, x] : ans)
printf("%d %d\n", y, x);
return 0;
}