- 飞跃原野
why?80
- 2024-10-30 20:58:34 @
#include <iostream>
#include <queue>
using namespace std;
struct node {
int x, y, s, d;
};
queue<node> que;
int m, n, d, check[105][105][105];
char map[105][105];
int dir[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
int main() {
cin >> n >> m>> d;
for (int i = 1; i <= n; i++) {
cin >> &map[i][1];
}
que.push({ 1,1,0,d });
for (int i = 0; i <= d; i++) {
check[1][1][i] = 1;
}
while (!que.empty()) {
node t = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int x = t.x + dir[i][0];
int y = t.y + dir[i][1];
if (x == n && y == m) {
cout << t.s + 1 << endl;
return 0;
}
if (map[x][y] == 'P' && check[x][y][t.d] == 0) {
check[x][y][t.d] = 1;
que.push({ x,y,t.s + 1,t.d });
}
for (int j = 2; j <= t.d; j++) {
int x = t.x + j * dir[i][0];
int y = t.y + j * dir[i][1];
if (x == n && y == m) {
cout << t.s + 1 << endl;
return 0;
}
if (map[x][y] == 0) break; //越界
if (map[x][y] == 'P' && check[x][y][t.d - j] == 0) {
check[x][y][t.d - j] = 1;
que.push({ x,y,t.s + 1,t.d - j });
}
}
}
}
cout << "impossible" << endl;
return 0;
}
1 条评论
-
majingchun LV 1 @ 2024-12-1 21:40:05
你哪道题,看起来有点像走迷宫,告诉我们吧
竟然用广搜做,怎么不先用深搜,太有实力了!!6🤣 1🤡 1
- 1
信息
- ID
- 584
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 69
- 已通过
- 6
- 上传者