题面描述

在一个 $n \times m$ 的 0-1 矩阵中，我们需要从第一列的任意一个 1 出发，找到到达最后一列任意一个 1 的最少步数。如果无法到达，则输出 -1。输入的第一行为两个整数 $n$ 和 $m$，接下来是 $n$ 行，每行包含 $m$ 个数，数值为 0 或 1。输出应为最短步数。

思路：多源BFS

多源BFS模板题：LeetCode 542. 01 矩阵

本题可以把第一列的所有元素为1的位置作为起点，将最后一列所有元素为1的位置作为终点，求起点到终点的最短距离，即为多源BFS

具体步骤：

1. 初始化起点：将第一列中所有值为 1 的位置作为起点，加入队列中。
2. BFS遍历：从队列中逐个取出节点，探索四个方向（上下左右），如果发现相邻位置的值为 1 且未被访问过，就将该位置加入队列并标记为已访问。
3. 终止条件：当遍历到最后一列时，输出当前步数。
4. 无解情况：如果队列为空仍未到达最后一列，输出 -1。

时间复杂度

$O(nm)$

代码

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义节点结构体，存储当前坐标和步数
struct Node {
    int x, y, step; // x, y 表示坐标，step 表示从起点到当前节点的步数
    Node(int _x, int _y, int _step) : x(_x), y(_y), step(_step) {}
};

int main() {
    int m, n;
    cin >> m >> n; // 输入矩阵的行数 m 和列数 n
    
    // 初始化矩阵和访问标记
    vector<vector<int>> grid(m, vector<int>(n)); // 存储矩阵
    vector<vector<bool>> visited(m, vector<bool>(n, false)); // 标记访问状态
    
    // 输入矩阵数据
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }
    
    queue<Node> q; // BFS 队列
    
    // 将第一列中的所有值为 1 的位置作为起点放入队列
    for (int i = 0; i < m; ++i) {
        if (grid[i][0] == 1) {
            q.push(Node(i, 0, 0)); // 起点坐标及初始步数为 0
            visited[i][0] = true; // 标记为已访问
        }
    }
    
    // 定义四个方向的移动 (上下左右)
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    // 开始 BFS 遍历
    while (!q.empty()) {
        Node current = q.front(); // 获取当前节点
        q.pop(); // 从队列中移除
        
        int x = current.x; // 当前 x 坐标
        int y = current.y; // 当前 y 坐标
        int step = current.step; // 当前步数
        
        // 检查是否到达最后一列
        if (y == n - 1 && grid[x][y] == 1) {
            cout << step << endl; // 输出步数
            return 0; // 结束程序
        }
        
        // 遍历四个方向
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir]; // 新的 x 坐标
            int ny = y + dy[dir]; // 新的 y 坐标
            
            // 检查新坐标是否在矩阵内且未被访问
            if (0 <= nx && nx < m && 0 <= ny && ny < n 
                && grid[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true; // 标记为已访问
                q.push(Node(nx, ny, step + 1)); // 将新节点加入队列
            }
        }
    }
    
    // 如果队列为空且未找到可达的终点，输出 -1
    cout << -1 << endl;
    
    return 0;
}

python代码

# 输入矩阵的行数 m 和列数 n
m, n = map(int, input().split())
grid = []  # 初始化矩阵

# 输入矩阵数据
for i in range(m):
    grid.append(list(map(int, input().split())))

# 深度优先搜索（DFS）相关的变量
dp = [[float('inf')] * n for _ in range(m)]  # dp数组，初始化为无穷大
res = [float('inf')]  # 结果数组，用于存储最短路径

def dfs(i, j, path, grid):
    # 检查边界条件：超出矩阵范围或遇到障碍（不是1）
    if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
        return
    
    # 如果到达最后一列，更新最短路径
    if j == n - 1:
        res[0] = min(res[0], path)
        return
    
    # 剪枝：如果当前路径长度已经不如最优解，直接返回
    if path >= res[0]:
        return
    
    # 剪枝：如果当前路径长度已经大于等于已记录的最短路径，返回
    if path >= dp[i][j]:
        return
    
    # 更新当前路径长度
    dp[i][j] = path
    grid[i][j] = 2  # 标记当前节点为已访问（设为2）

    # 递归调用四个方向的DFS
    dfs(i, j + 1, path + 1, grid)  # 向右
    dfs(i - 1, j, path + 1, grid)  # 向上
    dfs(i + 1, j, path + 1, grid)  # 向下
    dfs(i, j - 1, path + 1, grid)  # 向左

    grid[i][j] = 1  # 回溯，重置当前节点为未访问（设为1）

import copy

# 检查最后一列是否有可达的1
for j in range(n):
    flag = 0  # 标记是否找到可达的1
    for i in range(m):
        if grid[i][j] == 1:
            flag = 1  # 找到可达的1，标记为1
            break
    if flag == 0:
        print(-1)  # 如果没有找到1，则直接输出-1
        exit(0)

# 从第一列的所有1出发，执行DFS
for i in range(m):
    dfs(i, 0, 0, copy.deepcopy(grid))  # 深拷贝防止修改原始grid

# 检查结果并输出
if res[0] == float('inf'):
    print(-1)  # 如果没有找到可达的路径，输出-1
else:
    print(res[0])  # 输出最短路径长度

Java代码

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

// 定义一个记录类 Pair，用于存储节点的坐标和路径长度
record Pair(int x, int y, int path) {}

public class Main {
    // 定义移动方向：右、下、上
    final static int[][] move = {{0, 1}, {1, 0}, {-1, 0}};
    static int res; // 用于存储最短路径
    static int mat[][]; // 矩阵

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // 创建输入流
        int n = in.nextInt(); // 输入矩阵的行数
        int m = in.nextInt(); // 输入矩阵的列数
        mat = new int[n][m]; // 初始化矩阵

        // 输入矩阵数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mat[i][j] = in.nextInt(); // 读取矩阵每个位置的值
            }
        }

        res = 0x3f3f3f3f; // 将结果初始化为一个较大的数（无穷大）
        
        // 遍历第一列，寻找所有值为1的起点，进行 BFS
        for (int i = 0; i < n; i++) {
            if (mat[i][0] == 1) { // 只对第一列中的 1 进行 BFS
                bfs(i, n, m); // 从这个位置开始 BFS
            }
        }

        // 检查是否找到路径，未找到则输出 -1
        res = res == 0x3f3f3f3f ? -1 : res; 
        System.out.println(res); // 输出最短路径或 -1
    }

    static void bfs(int i, int n, int m) {
        boolean[][] v = new boolean[n][m]; // 初始化访问标记数组
        Queue<Pair> q = new ArrayDeque<>(); // 创建队列用于 BFS
        q.offer(new Pair(i, 0, 0)); // 将起点放入队列
        v[i][0] = true; // 标记起点为已访问

        // BFS 遍历
        while (!q.isEmpty()) {
            Pair p = q.poll(); // 取出队列中的节点
            int x = p.x(); // 当前节点的 x 坐标
            int y = p.y(); // 当前节点的 y 坐标
            int path = p.path(); // 从起点到当前节点的路径长度

            // 如果到达最后一列，更新最短路径
            if (y == m - 1) {
                res = Math.min(res, path);
            }

            // 遍历可能的移动方向
            for (int z = 0; z < 3; z++) {
                int xx = x + move[z][0]; // 计算新的 x 坐标
                int yy = y + move[z][1]; // 计算新的 y 坐标
                
                // 检查新的坐标是否在矩阵范围内且未被访问且为 1
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && !v[xx][yy] && mat[xx][yy] == 1) {
                    q.offer(new Pair(xx, yy, path + 1)); // 将新节点加入队列
                    v[xx][yy] = true; // 标记为已访问
                }
            }
        }
    }
}

题目描述

有一个$n*m$的01矩阵，你需要从第一列的任意一个1出发，到达最后一列的任意一个1。途径的点必须为1，求最少的步数。

输入描述

第一行两个整数$n,m$，代表两个有一个n行m列的01矩阵

接下来n行，每行m个数。每个数非0即1

输出描述

输出最短步数，当不可达时输出-1。

样例

输入

3 4
0 1 1 0
1 1 1 1
0 1 0 1

输出

3