兄弟们,我只能写到这了
2023-11-04 15:14:58
发布于:江苏
36阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point {
int x, y;
int turns; // 拐弯次数
};
int minTurns(vector<vector<int>>& map, int x1, int y1, int x2, int y2) {
int n = map.size();
int m = map[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
queue<Point> q;
q.push({x1, y1, 0});
visited[x1][y1] = true;
while (!q.empty()) {
Point curr = q.front();
q.pop();
if (curr.x == x2 && curr.y == y2) {
return curr.turns;
}
// 向上移动
for (int i = curr.x - 1; i >= 0; i--) {
if (map[i][curr.y] == 1) {
break; // 遇到高山,无法继续移动
}
if (!visited[i][curr.y]) {
q.push({i, curr.y, curr.turns + 1});
visited[i][curr.y] = true;
}
}
// 向下移动
for (int i = curr.x + 1; i < n; i++) {
if (map[i][curr.y] == 1) {
break; // 遇到高山,无法继续移动
}
if (!visited[i][curr.y]) {
q.push({i, curr.y, curr.turns + 1});
visited[i][curr.y] = true;
}
}
// 向左移动
for (int j = curr.y - 1; j >= 0; j--) {
if (map[curr.x][j] == 1) {
break; // 遇到高山,无法继续移动
}
if (!visited[curr.x][j]) {
q.push({curr.x, j, curr.turns + 1});
visited[curr.x][j] = true;
}
}
// 向右移动
for (int j = curr.y + 1; j < m; j++) {
if (map[curr.x][j] == 1) {
break; // 遇到高山,无法继续移动
}
if (!visited[curr.x][j]) {
q.push({curr.x, j, curr.turns + 1});
visited[curr.x][j] = true;
}
}
}
return -1; // 无法到达终点
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> map(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int minTurn = minTurns(map, x1, y1, x2, y2);
cout << minTurn << endl;
return 0;
}
全部评论 1
好的,数据已经正式上传到主题库了。可以再尝试提交一下看看。
2024-06-18 来自 浙江
0
有帮助,赞一个