能否用c++语言来写上述问题
时间: 2024-01-05 11:04:10 浏览: 65
读者写者问题c++实现
5星 · 资源好评率100%
当然可以,以下是同样功能的 C++ 代码实现,供你参考:
```c++
#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;
typedef pair<int, int> pii;
// 哈希函数
struct HashFunc {
size_t operator()(const pii& p) const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};
// 判断一个位置是否合法
bool is_valid(int x, int y, const unordered_set<pii, HashFunc>& obstacles) {
if (x < -100 || x > 100 || y < -100 || y > 100) return false;
if (obstacles.count({x, y})) return false;
return true;
}
// 广搜
int bfs(pii start, pii end, const unordered_set<pii, HashFunc>& obstacles) {
vector<pii> dirs = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
queue<pair<pii, int>> q;
unordered_set<pii, HashFunc> visited;
q.push({start, 0});
visited.insert(start);
while (!q.empty()) {
auto [pos, steps] = q.front();
q.pop();
if (pos == end) return steps;
for (auto [dx, dy] : dirs) {
int new_x = pos.first + dx, new_y = pos.second + dy;
if (is_valid(new_x, new_y, obstacles)) {
pii new_pos = {new_x, new_y};
if (!visited.count(new_pos)) {
q.push({new_pos, steps + 1});
visited.insert(new_pos);
}
}
}
}
return -1;
}
int main() {
int x_final, y_final;
cin >> x_final >> y_final;
int n;
cin >> n;
unordered_set<pii, HashFunc> obstacles;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
obstacles.insert({x, y});
}
pii start = {0, 0};
pii end = {x_final, y_final};
int res = bfs(start, end, obstacles);
if (res == -1) {
cout << "fail" << endl;
} else {
cout << res << endl;
}
return 0;
}
```
希望这份代码能够对你有所帮助!
阅读全文