题目描述

给定一个n×m的棋盘，（'*'）是障碍物，其余（'.'）是空格，要将皇后从（1，1）的位置向右，向下或向右下移动移动多步到右下角（n，m）的位置，移动路径上不能出现障碍物，求移动到右下角的最少步数。

解题思路

这种数据范围不算大的棋盘类求最短路径问题我们可以用bfs去遍历棋盘，针对这种一次可以沿一个方向走任意正整数步的题目，我们可以把每一次一条直线上的一串移动当成一步。

我们可以先设好方向数组（三个方向），在结构体上加个step记录步数，把起始点入队，然后遍历三个方向，从当前点向三个允许移动的方向发射射线，一直往前走（k=1，2，3...)；遇到障碍物或边界，射线停止（break），期间用check标记格子是否走过（避免重复入队）。

check数组的作用

以此为例

3 4

. . ..

**.*

. . ..

从（1,1）开始发起第一条射线将(1,2),(1,3),(1,4)都push进队列里面了，当取出第二个点 (1,3) (当前步数 = 1)，继续扩散。

• 方向0（向右）：同理，看 (1,4) 时发现 vis[1][4][0] 是 true，直接 break（vis 再次立功）。
• 方向1（向下）：从 (1,3) 向下走一步，到达 (2,3)。程序检查 vis[2][3][1]。因为之前并没有人从上方往下扫过 (2,3)，所以 vis[2][3][1] 是 false。程序把 vis[2][3][1] 设为 true。
• 重点来了， 接下来程序检查 check[2][3]。在刚才第二阶段时，(1,2) 向右下走，已经把 check[2][3] 设为 true 了！，并且 (2,3) 已经在队列里排队了。程序发现 check 是 true，于是不执行 q.push()，但循环继续往下扫描（如果下面还有格子的话）。
• check 的作用：点 (2,3) 既可以从 (1,2) 斜着走过来，也可以从 (1,3) 直着走过来。check 成功拦截了 (1,3) 的这次入队尝试，防止了 (2,3) 在队列中出现两次，也就是避免重复入队了，减少时间复杂度（当然，不设check在此题也可以通过，完善一点罢了）

核心剪枝（防超时）：用一个三维数组vis[x][y][dir] 记录“方向 dir 的射线是否已经穿过点 （x，y）。如果已经有同方向的射线扫过这里，说明前面的路线已经被探索过了，可以直接 break 停止当前射线的延伸。如果没有这个剪枝，空旷的棋盘会导致极大规模的重复计算，最终超时 (TLE)。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
typedef long long ll;
using namespace std;
char grid[2005][2005];//棋盘
bool vis[2005][2005][3];//剪枝数组，记录不同方向的射线
int check[2005][2005];//检查格子有没有被扫过，防止重复入队
int n, m;
struct point {
	int x, y, step;
};
int dx[] = { 1,0,1 };//方向数组
int dy[] = { 0,1 ,1 };
int final_step;
bool flag;
void bfs(int stx,int sty) {
	queue<point> q;
	q.push({ stx,sty,0});//将起始点入队

	while (!q.empty()) {
		point cur = q.front();
		q.pop();
		if (cur.x == n && cur.y == m) {//当抵达终点时，就已经是最短路径了
			final_step = cur.step;
			flag = true;
			return;
		}
		for (int i = 0; i < 3; ++i) {//遍历三个方向
			for (int k = 1;; ++k) {//射线
				int nx = cur.x + dx[i] * k;
				int ny = cur.y + dy[i] * k;
				if (nx > n || ny > m || grid[nx][ny] == '*') {//遇到障碍物或边界，射线停止
					break;
				}
				if (vis[nx][ny][i]) {//如果是相同方向，射线停止
					break;
				}

				vis[nx][ny][i] = true;//存在不同方向，标记并入队
				if (!check[nx][ny]) {
					check[nx][ny] = true;//检查这个格子有没有被射线扫过
					q.push({ nx,ny,cur.step + 1 });//入队，如果是不同方向，step+1
				}
			}
			
			
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> grid[i][j];
		}
	}
	bfs(1, 1);
	if (flag) cout << final_step;
	else cout << -1;
}

代码模拟（部分）

如果是这种情况，这段代码怎么确保最短路径？

主打的就是先到先得