解题思路

状态设计

这个问题的本质是带状态的最短路/BFS：

• 普通BFS每个格子只需记录是否访问过，但现在要记录“到达该格子的上一动方向”。
• 因为移动方向交替，上一步“竖”（上下）只能现在“横”，上一步“横”只能现在“竖”。

状态变量

• $pos(x, y)$：当前坐标

• $dir$：到达此格子的上一步方向类型，分为两种：

  • 0：上一动为竖向（上下）
  • 1：上一动为横向（左右）
  • 2：起点（允许四个方向，第一步可以任选）

所以，$vis[x][y][dir]$ 表示“到达 $(x, y)$ 并且上一动为 dir 的状态是否访问过”。

BFS建模

1. 起点入队（$x\_s, y\_s, dir=2, step=0$）。

2. 每次出队($x,y,dir,step$)，根据 $dir$ 的不同，决定下一步能走的方向：

   • dir=2（初始），可走上下左右；
   • dir=0（上一动竖向），只能左右；
   • dir=1（上一动横向），只能上下；

3. 若到达终点，返回步数。

4. 若队列为空，输出-1。

复杂度分析

• 状态总数 $O(nm\times3)$，每个状态最多访问一次。
• BFS时间复杂度 $O(nm)$，可以通过$n,m\leq2000$。

代码实现

Python 实现

from collections import deque

n, m = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
g = [input().strip() for _ in range(n)]

# 上下左右四个方向
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 对应方向属于竖(0):上下，横(1):左右
dir_type = [0,0,1,1]

from sys import exit

vis = [[[False]*3 for _ in range(m)] for _ in range(n)]
q = deque()
# 起点状态，方向2代表初始未走过
q.append((x1, y1, 2, 0))
vis[x1][y1][2] = True

while q:
    x, y, lastd, step = q.popleft()
    if x == x2 and y == y2:
        print(step)
        exit(0)
    for d in range(4):
        # 只有满足交替方向的才能走
        if lastd == 2 or dir_type[d] != lastd:
            nx, ny = x+dx[d], y+dy[d]
            if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == '.':
                ndir = dir_type[d]
                if not vis[nx][ny][ndir]:
                    vis[nx][ny][ndir] = True
                    q.append((nx, ny, ndir, step+1))
print(-1)

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static char[][] g;
    static int[] dx = {-1, 1, 0, 0}; // 上下左右
    static int[] dy = {0, 0, -1, 1};
    static int[] dirType = {0,0,1,1}; // 0竖，1横
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        int x1 = Integer.parseInt(s2[0])-1, y1 = Integer.parseInt(s2[1])-1;
        int x2 = Integer.parseInt(s2[2])-1, y2 = Integer.parseInt(s2[3])-1;
        g = new char[n][m];
        for (int i = 0; i < n; i++) g[i] = br.readLine().toCharArray();
        boolean[][][] vis = new boolean[n][m][3];
        Queue<int[]> q = new ArrayDeque<>();
        // 起点状态，2代表初始
        q.add(new int[]{x1, y1, 2, 0});
        vis[x1][y1][2] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], lastd = cur[2], step = cur[3];
            if (x == x2 && y == y2) {
                System.out.println(step);
                return;
            }
            for (int d = 0; d < 4; d++) {
                if (lastd == 2 || dirType[d] != lastd) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx>=0 && nx<n && ny>=0 && ny<m && g[nx][ny]=='.') {
                        int ndir = dirType[d];
                        if (!vis[nx][ny][ndir]) {
                            vis[nx][ny][ndir] = true;
                            q.add(new int[]{nx, ny, ndir, step+1});
                        }
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

C++ 实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 2005;
char g[N][N];
bool vis[N][N][3];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
// 0:竖,1:横
int dirType[4] = {0,0,1,1};

int main() {
    int n, m;
    cin >> n >> m;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    --x1; --y1; --x2; --y2;
    for (int i=0; i<n; i++) cin >> g[i];
    queue<tuple<int,int,int,int>> q;
    q.emplace(x1, y1, 2, 0);
    vis[x1][y1][2] = true;
    while (!q.empty()) {
        auto [x, y, lastd, step] = q.front(); q.pop();
        if (x == x2 && y == y2) {
            cout << step << endl;
            return 0;
        }
        for (int d=0; d<4; d++) {
            if (lastd==2 || dirType[d]!=lastd) {
                int nx = x+dx[d], ny = y+dy[d];
                if (nx>=0 && nx<n && ny>=0 && ny<m && g[nx][ny]=='.') {
                    int ndir = dirType[d];
                    if (!vis[nx][ny][ndir]) {
                        vis[nx][ny][ndir] = true;
                        q.emplace(nx, ny, ndir, step+1);
                    }
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

题目内容

给定一张$n×m$的网格图，每个网格可以是“空地” 或者“障碍”“空地” 用$.$表示，“障碍”用$x$表示。

约定从上至下第$1$行，从左至右第$j$列的网格表示为$(i,j)$

此外，一个起点和一个终点被给定，保证起点和终点均为空地。

在起点处，有一个机器人，它想要前往终点。在机器人原本的设定中，假设它当前在$(x,y)$，则它可以选择向上下左右四个方向移动一格，到达$(x,y+1),(x,y-1),(x-1,y)$或是$(x+1,y)$。

当然，机器人在移动的过程中不能经过障碍(在每一步移动中，移动前后所处的网格都需要是空地)，也不能从网格边界离开。

可惜的是，这台机器人因为年代久远，不可避免地发生了机械故障。

故障表现在:

如果它上一步选择了向上或者向下移动，则当前只能选择向左或者向右移动;

如果它上一步选择了向左或者向右移动，则当前只能选择向上或者向下移动。

形式化的，设机器人的行动轨迹按顺序依次是$P_1.P_2...P_k$(包含起点和终点)。则不存在两点$p_i(x_i,y_i)$和$p_j(x_j,y_j)$同时满足$|i-j|=2$且$max(|x_i-x_j|,|y_i-y_j|)=2$

请你回答，这台故障的机器人从起点走到终点至少需要几步呢?

当然，障碍的存在使得它有可能永远也无法抵达终点。此时，请输出$-1$

输入描述

第一行两个正整数$n$和$m$。

第二行四个正整数$x_{s'}y_{s'}x_{T'}y_T(1≤x_{s'}x_T≤n,1≤y_{s'}y_T≤m)$，分别表示起点和终点的坐标。其中，起点的坐标是$(x_{s'}y_s)$，终点的坐标是$(x_T,y_T)$。

接下来$n$ 行，每行一个长为$m$的字符串，表示网格图。

保证给出的所有$n×m$个字符只会是$.$(空地)或者$X($障碍)，且起点和终点一定是空地。

注意，起点和终点有可能重合。

$1≤n,m≤2000$

输出描述

输出一行，一个整数，表示机器人从起点出发抵达终点所需的最小步数。

样例1

输入

4 4
1 3 4 3
X...
..XX
..X.
X..X

输出

7

说明

一种可行的机器人移动路径如下 $(1,3)→(1,2)→(2,2)→(2,1)→(3,1)-(3,2)→(4,2)→(4,3)$ 可以证明不存在更短的路径。

样例2

输入

4 4
1 4 4 3
X...
..XX
..X.
X..X

输出

-1

说明

机器人第一步只能走 $(1,4)→(1,3)$ ，之后无路可走，无法到达终点,故输出 $-1$ 。