re不是这道题你什么意思啊
原题链接:292.最少转弯问题2024-05-28 12:56:50
发布于:广东
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 1e9;
int n, m;
int map[MAXN][MAXN];
int dx[4] = {0, 1, 0, -1}; // 方向数组,右、下、左、上
int dy[4] = {1, 0, -1, 0};
int dist[MAXN][MAXN][105]; // 距离数组,记录每个位置每个方向的最小拐弯次数
struct State {
int x, y, dir, turns;
};
bool isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0;
}
int bfs(int x1, int y1, int x2, int y2) {
queue<State> q;
for (int i = 0; i < 4; ++i) {
dist[x1][y1][i] = 0;
q.push({x1, y1, i, 0});
}
while (!q.empty()) {
State curr = q.front();
q.pop();
if (curr.x == x2 && curr.y == y2) {
return curr.turns;
}
for (int i = 0; i < 4; ++i) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
int nturns = curr.turns + (curr.dir != i ? 1 : 0);
if (isValid(nx, ny) && dist[nx][ny][i] > nturns) {
dist[nx][ny][i] = nturns;
q.push({nx, ny, i, nturns});
}
}
}
return INF; // 如果无法到达终点,返回一个很大的数
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> map[i][j];
for (int k = 0; k < 4; ++k) {
dist[i][j][k] = INF;
}
}
}
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int result = bfs(x1 - 1, y1 - 1, x2 - 1, y2 - 1);
cout << (result == INF ? -1 : result) << endl;
return 0;
}
全部评论 4
好的,数据已经正式上传到主题库了。可以再尝试提交一下看看。
2024-06-18 来自 浙江
0以后数据有问题可以在这个帖子下留言。https://www.acgo.cn/discuss/18339。
2024-05-30 来自 新加坡
0题目有问题,数据全是错的。
2024-05-28 来自 新加坡
06
2024-05-28 来自 广东
0我新数据已经改好了,明天小鱼老师应该会传上新的数据。到时候再试一下。
2024-05-28 来自 新加坡
0
?什么GPT不用vector(
2024-05-28 来自 广东
0傻
2024-05-28 来自 广东
0你家gpt这么牛啊
2024-05-28 来自 广东
0
有帮助,赞一个