• 为什么会 wa 呢
• 试一试这组数据

2 3 2
1 1 2 3
..@
...

• 答案应该是 2

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int n, m, k, x1, y1, x2, y2;
	cin >> n >> m >> k >> x1 >> y1 >> x2 >> y2;
	x1--, y1--, x2--, y2--;
	vector<string> g(n);
	for (int i = 0; i < n; i++) cin >> g[i];
	
	vector<int> dx = {0, 1, 0, -1};
	vector<int> dy = {1, 0, -1, 0};
	vector<vector<int>> d(n, vector<int>(m, -1));
	queue<pair<int, int> > q;
	q.push({x1, y1}), d[x1][y1] = 0;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		
		// 先枚举方向，再枚举长度
		for (int j = 0; j < 4; j++) {
			for (int p = 1; p <= k; p++) {
				int u = x + p * dx[j], v = y + p * dy[j];
				
				// d[u][v] != -1 就直接 break
				if (u < 0 || u >= n || v < 0 || v >= m || g[u][v] == '@' || d[u][v] != -1) break;
				d[u][v] = d[x][y] + 1;
				q.push({u, v});
			}
		}
	}
	cout << d[x2][y2] << '\n';
	
	return 0;
}

• 为什么会 TLE 呢
• 迷宫大小 $h \times w$ 最大是 $10^6$
• 每次的最大步长 $k$，最大也是 $10^6$

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int n, m, k, x1, y1, x2, y2;
	cin >> n >> m >> k >> x1 >> y1 >> x2 >> y2;
	x1--, y1--, x2--, y2--;
	vector<string> g(n);
	for (int i = 0; i < n; i++) cin >> g[i];
	
	vector<int> dx = {0, 1, 0, -1};
	vector<int> dy = {1, 0, -1, 0};
	vector<vector<int>> d(n, vector<int>(m, -1));
	queue<pair<int, int>>  q;
	q.push({x1, y1}), d[x1][y1] = 0;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		
		// 先枚举方向，再枚举长度
		for (int j = 0; j < 4; j++) {
			for (int p = 1; p <= k; p++) {
				int u = x + p * dx[j], v = y + p * dy[j];
				if (u < 0 || u >= n || v < 0 || v >= m || g[u][v] == '@') break;
				if (d[u][v] == -1) {
					d[u][v] = d[x][y] + 1;
					q.push({u, v});
				}
			}
		}
	}
	cout << d[x2][y2] << '\n';
	
	return 0;
}