题解：P9351 [JOI 2023 Final] Maze

太摆了丢个代码跑路：

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e7 + 10;

vector<vector<bool>> g;

int n, m, k, sx, sy, tx, ty;
vector<vector<bool>> st;
vector<vector<int>> dis;

const int dx[] = {0, 1, 0, -1, -1, -1, 1, 1}, dy[] = {1, 0, -1, 0, -1, 1, -1, 1};

bool chk(int x, int y) {
	return x >= 1 && y >= 1 && x <= n && y <= m;
}

struct Node {
	int x, y, cost, r;
	
	bool operator >(const Node& h) const {
		return cost == h.cost ? r < h.r : cost > h.cost;
	}
};

void bfs(int x, int y) {
	st.resize(n + 2);
	dis.resize(n + 2);
	for (int i = 1; i <= n; ++ i ) {
		st[i].resize(m + 2);
		dis[i].resize(m + 2);
	}
	
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= m; ++ j ) {
			st[i][j] = false;
			dis[i][j] = 1e9;
		}
	
	priority_queue<Node, vector<Node>, greater<Node>> q;
	q.push({x, y, 0, 0});
	dis[x][y] = 0;
	
	while (q.size()) {
		int x = q.top().x, y = q.top().y, r = q.top().r;
		q.pop();
		
		if (st[x][y]) continue;
		st[x][y] = true;
		
		if (!r) {
			for (int i = 0; i < 4; ++ i ) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (chk(nx, ny) && dis[nx][ny] > dis[x][y] + g[nx][ny]) {
					dis[nx][ny] = dis[x][y] + g[nx][ny];
					q.push({nx, ny, dis[nx][ny], g[nx][ny] ? k - 1 : 0});
				}
			}
		}
		else {
			for (int i = 0; i < 8; ++ i ) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (chk(nx, ny) && dis[nx][ny] > dis[x][y]) {
					dis[nx][ny] = dis[x][y];
					q.push({nx, ny, dis[nx][ny], r - 1});
				}
			}
		}
	}
	
	return;
}

int main() {
//	freopen("maze4.in", "r", stdin);
//	freopen("maze.out", "w", stdout);
	
	cin >> n >> m >> k >> sx >> sy >> tx >> ty;
	
	g.resize(n + 2);
	for (int i = 1; i <= n; ++ i ) {
		g[i].resize(m + 2);
		for (int j = 1; j <= m; ++ j ) {
			char c;
			cin >> c;
			g[i][j] = c == '#';
		}
	}
	
	bfs(sx, sy);
	cout << dis[tx][ty] << '\n';
	
	return 0;
}
```

正在渲染内容...