#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 条评论

  • @ 2024-12-1 21:40:05

    你哪道题,看起来有点像走迷宫,告诉我们吧竟然用广搜做,怎么不先用深搜,太有实力了!!6

    🤣 1
    🤡 1
    • 1

    信息

    ID
    584
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    69
    已通过
    6
    上传者