3 solutions

  • 0
    @ 7 months ago

    第一次水灵灵的写出来了！记录一下

    #include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m));
    queue<pair<int,int>> q;
    vector<vector<int>> d(n,vector<int>(m,INT_MAX));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin>>grid[i][j];
        }
        if(grid[i][0]==1){
            q.push({i,0});
            d[i][0]=0;
        }
    }
    int dx[3]={0,-1,1};
    int dy[3]={1,0,0};
    while (!q.empty()) {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for (int i=0; i<3; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx<0||nx>=n||ny<0||ny>=m||d[nx][ny]!=INT_MAX||grid[nx][ny]==0) {
             continue;
            }
            d[nx][ny]=d[x][y]+1;
            q.push({nx,ny});
        }
    }
    int res=INT_MAX;
    for (int i = 0; i < n; i++) {
        if (grid[i][m-1]==1&&d[i][m-1]!=INT_MAX) {
                res=min(res,d[i][m-1]);
        }
    }
    if(res==INT_MAX){
        cout<<-1<<endl;
    }else{
        cout<<res<<endl;
    }


}
    Copy
    • 0
      @ 7 months ago

      多源DFS，从第一列的每一个1出发进行遍历，同时也创建一个数组dis来记录距离，最后对dis的最后一列进行遍历，如果最小值为初始值，那么就认为没法到达，否则输出最短的路径。

      #include <cstdint>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int dir[3][2]={-1,0,0,1,1,0};
void dfs(vector<vector<int>>& graph,vector<vector<int>>& dis){
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        if(graph[i][0]==1){
            q.push({i,0});
            dis[i][0]=0;
        }
    }
    while(!q.empty()){
        auto cur=q.front();
        q.pop();
        int x=cur.first;
        int y=cur.second;
        for(int i=0;i<3;i++){
            int curx=x+dir[i][0];
            int cury=y+dir[i][1];
            if(curx<0||curx>=n||cury<0||cury>=m||dis[curx][cury]!=1001||graph[curx][cury]==0)continue;
            dis[curx][cury]=dis[x][y]+1;
            q.push({curx,cury});
        }
    }
}

int main(){
    cin>>n>>m;
    vector<vector<int>> graph(n,vector<int>(m,0));
    vector<vector<int>> dis(n,vector<int>(m,1001));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>graph[i][j];
        }
    }
    dfs(graph,dis);
    int res=1000;
    for(int i=0;i<n;i++){
        if(dis[i][m-1]<res)res=dis[i][m-1];
    }
    int ans=(res==1000)?-1:res;
    cout<<ans<<endl;
}
      Copy
      • 0
        @ 9 months ago

        题面描述

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

        思路：多源BFS

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

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

        具体步骤：

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

        时间复杂度

        O(nm)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;
}
        Copy

        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])  # 输出最短路径长度
        Copy

        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; // 标记为已访问
                }
            }
        }
    }
}
        Copy
        • 1

        2023.09.20-秋招-第二题-传球

        Information

        ID
        56
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        4
        Tags
        # Submissions
        305
        Accepted
        74
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 京ICP备2025123107号-1
        3. Worker 0, 224ms
        4. Powered by Hydro v4.18.0 Community