#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;
}

4 条评论

  • @ 2026-4-9 13:27:19

    1.开O2 2.数组开大点

    • @ 2026-4-9 13:27:04

      先开O2优化,再给数组开大一点点点点就行

      👀 1
      🕊️ 1
      🤡 1
      • @ 2026-4-8 20:45:05

        牢是改数据了

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

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

        🤡 3
        🤣 2
        • 1

        信息

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