首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路

热度指数：2022 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个包含非负整数的 M x N 迷宫，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或者向右移动一步。

输入描述:

第一行包含两个整数M和N，以空格隔开，1≤N≤10，1≤N≤10。

接下来的M行中，每行包含N个数字。

输出描述:

找出总和最小的路径，输出路径上的数字总和。

示例1

输入

输出

算法知识视频讲解

JavaScript

sxc666

var rowCol = readline().split(" ").map(Number)
var row = rowCol[0]
var col = rowCol[1]
var matrix = []
while(line = readline()){
    var arr = line.split(" ").map(Number)
    matrix.push(arr)
}
print(fistResult(row,col,matrix))
function fistResult(row, col, matrix) {
        var sum = 0
        var dp = []
        for (let i = 0; i < row; i++) {
            dp[i]=[]
            for (let j = 0; j < col; j++) {
                if (i == 0 && j == 0) {
                    dp[0][0] = matrix[0][0]  
                }
                else if (i == 0 && j != 0) {
                    //j为0只能向右移动
                    dp[i][j] = dp[i][j - 1] + matrix[i][j] 
                }
                else if (i != 0 && j == 0) {
                    //i为0只能向下
                    dp[i][j] = dp[i - 1][j] + matrix[i][j]
                }
                else {
                    //i、j都不为0取向下向右最小的
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]
                }
            }
        }
        return dp[row - 1][col - 1]
}

发表于 2020-03-10 21:39:01 回复(0)

AIcodingRobot

let [m, n] = readline().split(' ').map(Number)

let dp = []

// 先保存矩阵到dp数组中
for(let i = 0; i < m; i++) {
    dp[i] = readline().split(' ').map(Number)
}

// dp初始化第一列
for(let i = 1; i < m; i++) {
    dp[i][0] = dp[i-1][0] + dp[i][0]
}

// dp初始化第一行
for(let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i-1] + dp[0][i]
}

// dp状态转移
for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + dp[i][j]
    }
}

print(dp[m-1][n-1])

编辑于 2022-05-21 20:44:47 回复(0)

lotianveo

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    const int maxv = 11;
    int dp[maxv][maxv];
    int A[maxv][maxv];
    int m, n;
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m;i++){
        for (int j = 1; j <= n;j++){
            scanf("%d", &A[i][j]);
        }
    }
    dp[1][1] = A[1][1];
    for (int i = 2; i <=m;i++){
        dp[i][1] = dp[i - 1][1] + A[i][1];
    }
    for (int i = 2; i <= n;i++){
        dp[1][i] = dp[1][i - 1] + A[1][i];
    }
 
        for (int i = 2; i <= m; i++)
        {
            for (int j = 2; j <= n; j++)
            {
                dp[i][j] = min(dp[i][j - 1],dp[i-1][j]) + A[i][j];
            }
        }
        printf("%d", dp[m][n]);
        return 0;
}

动态规划递推思路，dp[i][j]为(i,j)存的最短路径。

发表于 2021-08-21 21:24:44 回复(0)

Eldon_Chen

var lines = readline().split(' ');
var M = parseInt(lines[0]);
var N = parseInt(lines[1]);
 
var mat = new Array()
var res = new Array()
 
for(let i = 0 ; i < M ; i++){
    let lines = readline().split(' ');
    mat[i] = new Array()
    res[i] = new Array()
    for(let j = 0 ; j < N ; j ++){
        mat[i][j] = parseInt(lines[j])
        res[i][j] = -1
    }
}
 
var _MAX = function(i,j){
    if(i==M-1 && j==N-1) return mat[i][j]
    else if(i == M-1) return mat[i][j] + MAX(i,j+1)
    else if(j == N-1) return mat[i][j] + MAX(i+1,j)
    else return mat[i][j] + Math.min(MAX(i,j+1),MAX(i+1,j))
}
 
var MAX = function(i,j){
    if(res[i][j] == -1){
        res[i][j] = _MAX(i,j)
        return res[i][j]
    }
    else return res[i][j]
}
 
print(MAX(0,0))

发表于 2020-04-21 17:11:19 回复(0)

夏花爱秋叶

var line=readline().split(' ').map(Number)
            var myx=line[0]-1
            var myy=line[1]-1
            var temy=myy;
            var arr=[]
            while(temy>=0){
                 arr.push(readline().split(' ').map(Number));
                 temy--;
            }
            var min=10000000000000000000;
            function call(num,x,y){
                if(x==myx){
                    path(num,false,x,y)
                }else if(y==myy){
                    path(num,true,x,y)
                }else{
                    path(num,false,x,y)
                    path(num,true,x,y)
                }
            }
            function path(num,flag,x,y){
                // 向右
                if(flag){
                    if(x==myx){
                        // 符合条件则退出
                        if(y==myy){
                            min=num<min?num:min;
                            return ;
                        }
                        // 执行向下
                        call(num,x,y)
                    }else{
                        x++;//1 2
                        num+=arr[x][y];//1+3+1
                        call(num,x,y);// 5 2 0
                    }
                }else{
                    // 向下
                    if(y!=myy){
                        y++;// 1 2
                        num+=arr[x][y];// 6 7
                        call(num,x,y);// 6 2 1 7 2 2
                    }else if(y==myy){
                        min=num<min?num:min;
                        // console.log(min)
                        return ;
                    }
                }
            }
            call(arr[0][0],0,0)
            print(min)

发表于 2020-03-06 23:18:56 回复(0)

萌萌萌哒

JavaScript 2020美团-迷宫寻路😎dp

leetcode 64最小路径和

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
    if(!line) return
    inArr.push(line.trim())
    let mn = inArr[0].split(' ').map(e=>+e)
    let m = mn[0]
    let n = mn[1]
    if(inArr.length === m+1){
        let arr = []
        for (let i = 0; i < m; i++) {
            arr[i] = inArr[i+1].split(' ').map(e => +e)
        }
        console.log(minPathSum(arr))

    }
})

var minPathSum = function (grid) {
    const m = grid.length,
        n = grid[0].length
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i + 1 < m && j + 1 < n) {
                grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1])
            } else if (i + 1 < m) {
                grid[i][j] += grid[i + 1][j]
            } else if (j + 1 < n) {
                grid[i][j] += grid[i][j + 1]
            }
        }
    }
    return grid[0][0]
};

发表于 2020-03-08 18:42:23 回复(1)

AhaAha

let firstRow = readline().split(" ");

let m = firstRow[0];//行数

let n = firstRow[1];//列数

let arr = [];

for (let i = 0; i < m; i++) {

arr[i] = readline().split(" ").map(Number);

}

if (m == 1 || n == 1) {

print(arr[m - 1][n - 1]);

} else {

//存储数组中每个元素路径的最小值

let minArr = [];

for (let i = 0; i < m; i++) {

let temp = [];

for (let j = 0; j < n; j++) {

temp.push(0);

}

minArr.push(temp);

}

let minSum = 0;

// 从下往上遍历（行）

for (let i = m - 1; i >= 0; i--) {

// 从右到左遍历（列）

for (let j = n - 1; j >= 0; j--) {

if (i == m - 1 && j == n - 1) {

minArr[i][j] = arr[i][j];

} else if (i == m - 1) {

minArr[i][j] = minArr[i][j + 1] + arr[i][j];

} else if (j == n - 1) {

minArr[i][j] = minArr[i + 1][j] + arr[i][j];

} else {

if (minArr[i + 1][j] > minArr[i][j + 1]) {

minArr[i][j] = minArr[i][j + 1] + arr[i][j];

} else {

minArr[i][j] = minArr[i + 1][j] + arr[i][j];

}

print(minArr[0][0])

}

发表于 2020-03-13 17:04:55 回复(0)

JavaScript

巨人张

本题来自LeetCode原题：64. 最小路径和

(function() {
    let firstRow = readline().split(" ");
    let m = firstRow[0]; //行数
    let n = firstRow[1]; //列数

    let dp = [];
    //填充dp数组，并转为number类型
    for (var i = 0; i < m; i++) {
        dp[i] = readline().split(" ").map(v => Number(v));
    }
    //处理第一列
    for (var i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i][0];
    }
    //处理第一行
    for (var i = 1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + dp[0][i];
    }
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];
        }
    }
    print(dp[m - 1][n - 1]);
})();

编辑于 2021-10-30 21:56:00 回复(0)

JavaScript

牛客462983015号

没搞懂网站上怎么调试

var minPathSum = function(m, n, grid) {
    function f(h=0, l=0){
        if(h==0 && l==0){
            return grid[0][0]
        }
        if(h==0) {
            return result[l-1] + grid[0][l]
        }
        if(l==0) {
            return result[(h-1)*m] + grid[h][0]
        }
        return Math.min(result[(h-1)*l+l], result[h*l+l-1]) + grid[h][l]
    }
    const result=[]
    for(let i=0; i<m; i++){
        for(let j=0; j<n; j++){
            result[n*i+j] = f(i, j)
        }
    }
    return result[result.length-1]
};

编辑于 2020-10-21 11:09:39 回复(1)

小橙子&

动态规划解决问题

m,n =list(map(int,input().strip(' ').split(' ')))
matrix =[[] for _ in range(m)]
for i in range(m):
    data = list(map(int,input().strip(' ').split(' ')))
    matrix[i] = data
dp = [[0] * n for _ in range(m)]
dp[0][0] = matrix[0][0]
for i in range(1,n):
    dp[0][i] = dp[0][i-1] + matrix[0][i]
for i in range(1,m):
    dp[i][0] = dp[i-1][0] + matrix[i][0]
for i in range(1,m):
    for j in range(1,n):
        dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]
print(dp[-1][-1])

发表于 2020-08-22 12:03:44 回复(0)

恋浅笑

#include <iostream>
#include <vector>
#include <limits.h>
int main()
{
    int row = 0, col = 0;
    std::cin >> row >> col;
    std::vector<std::vector<int>> v(row, std::vector<int>(col, 0));
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            int tmp = 0;
            std::cin >> tmp;
            v[i][j] = tmp;
        }
    }
    //这里给的默认只是INT_MAX，之前是求最大值，所以默认值是0.
    //不然在处理第一行或者第一列的时候，不会加上之前的路径的dp，因为比较之后最小值都是0
    std::vector<std::vector<int>> dp(row + 1, std::vector<int>(col + 1, INT_MAX));
    dp[1][1] = v[0][0];
    for (int i = 1; i <= row; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            if (i == 1 && j == 1)
            {
                continue;  //这里要用continue不能使用break，不然不会执行j++操作
            }
            //特殊处理一下i==1和j == 1的情况，因为此时的dp[0][1] 和dp[1][0]
            //都是最大值，所以比较之后再相加会越界
            dp[i][j] = v[i - 1][j - 1] + std::min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    std::cout << dp[row][col] << std::endl;
    return 0;
}

发表于 2022-08-14 21:26:41 回复(0)

牛客238341157号

let line = readline().split(' ')
let m = parseInt(line[0])
let n = parseInt(line[1])

let arr = []
//获取输入的数组
for(let i = 0; i < m; i++) {
    arr[i] = readline().split(' ').map(Number)
}
//初始化dp二维数组，使其每个元素为Infinity无穷大
let dp = Array.from(Array(m)).map(() => Array(n).fill(Infinity))

// 计算第一列的dp值
for(let i = 0; i < m; i++) {
    let sum = 0
    for(let j = 0; j <=i; j++){
        sum += arr[j][0]
    }
    dp[i][0] = sum
}
// 计算第一行的dp值
for(let i = 0; i < n; i++) {
    let sum = 0
    for(let j = 0; j <=i; j++){
        sum += arr[0][j]
    }
    dp[0][i] = sum
}
// m×n可分解成(m-1)×n和m×(n-1)两部分，取其中较小值。
for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
        dp[i][j] = Math.min(arr[i][j]+dp[i-1][j], arr[i][j]+dp[i][j-1])
    }
}
console.log(dp[m-1][n-1])

发表于 2021-08-27 15:21:25 回复(0)

牛客748799536号

function getMigong(m,n,arr){
    var dp = [];
    for(var i = 0;i<=m;i++){
        dp[i] = new Array(n+1).fill(0);
    }
    for(var i = 1;i<=m;i++){
        for(var j = 1;j<=n;j++){
            if(i==1){
                dp[i][j] = dp[i][j-1]+arr[i-1][j-1]
            }
            else if(j==1){
                dp[i][j] = dp[i-1][j]+arr[i-1][j-1]
            }else{
                dp[i][j] =Math.min(dp[i-1][j],dp[i][j-1])+arr[i-1][j-1];
            }
        }
    }
    console.log(dp)
}

发表于 2021-08-10 19:53:05 回复(0)

拜仁的月饼

#include <vector>
#include <cstdio>
#include <numeric>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> maze){
    if(maze.empty())
        return 0;

    // 递归停止条件1：如果是刚好只有一行
    if(maze.size() == 1)
        return accumulate(maze[0].begin(), maze[0].end(), 0);
    
    // 递归停止条件2：如果是刚好只有一列
    if(maze[0].size() == 1){
        auto res = 0;
        for(vector<int> pane : maze)
            res += pane[0];
        
        return res;
    }

    // 向右访问之后的子向量
    vector<vector<int>> rightSub;
    for(vector<int> row : maze){
        vector<int> everyRow {row.begin() + 1, row.end()};
        rightSub.push_back(everyRow);
    }

    // 向下访问之后的子向量
    vector<vector<int>> downSub {maze.begin() + 1, maze.end()};

    return maze[0][0] + min(solution(downSub), solution(rightSub));
}

int main(){
    // M是行，N是每行N个数字
    int M, N;
    scanf("%d", &M);
    scanf("%d", &N);
    
    vector<vector<int>> maze;
    
    int elem = 0;
    
    for(int i = 0; i < M; i++){
        vector<int> row;
        for(int j = 0; j < N; j++){
            scanf("%d", &elem);
            row.push_back(elem);
        }
        maze.push_back(row);
    }
    
    printf("%d\n", solution(maze));
    
    return 0;
}

# coding=utf-8

from sys import stdin, stdout

def solution(maze):
    if not maze:
        return 0
    
    if len(maze) == 1:
        return sum(maze[0])
    
    if len(maze[0]) == 1:
        res = 0
        for pane in maze:
            res += pane[0]
        return res
    
    return maze[0][0] + min(solution(maze[1::]), solution([row[1::] for row in maze]))

if __name__ =='__main__':
    m_n = list(map(int,stdin.readline().strip().split()))
    
    maze = list()
    for i in range(m_n[0]):
        row = list(map(int, stdin.readline().strip().split()))
        maze.append(row)
    
    stdout.write("%d\n"%(solution(maze)))

编辑于 2021-08-09 23:38:20 回复(1)

勇敢牛牛不怕困难j

let [m,n] = readline().split(" ").map(Number);
var arr = [];
for(let i=1;i<=m;i++){
    arr[i] = readline().split(" ").map(Number);
    arr[i].unshift(0);
}
function fn1(m,n,arr){
    let dp = new Array(m+1);
    for(let i=0;i<=m;i++){
        dp[i] = new Array(n+1);
    }
    for(let i=0;i<=n;i++) dp[0][i] = Infinity;
    for(let i=0;i<=m;i++) dp[i][0] = Infinity;
    dp[0][1] = dp[1][0] = 0;
    for(let i=1;i<=m;i++){
        for(let j=1;j<=n;j++){
            dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
        }
    }
    console.log(dp[m][n]);
}
fn1(m,n,arr);

发表于 2020-12-15 21:36:25 回复(0)

洱海（▿）

发表于 2020-09-13 18:02:42 回复(0)

圆圆家的小源源

var firstLine = readline().split(' ')
var rows = parseInt(firstLine[0]);
var cols = parseInt(firstLine[1]);
var grid = [];
var line;
while(line = readline()){
    grid.push(line.split(' ').map(Number))
}

    var dp = Array.from(new Array(rows),()=> new Array(cols));
    for(var i = rows-1; i>=0;i--){
        for(var j = cols-1; j>=0;j-- ){
            if(i== rows-1 && j == cols-1){
                dp[i][j] = grid[i][j];
            }else if(i == rows-1&&j!=cols-1){
                dp[i][j] = grid[i][j] + dp[i][j+1];
            }else if(i != rows-1&&j==cols-1){
                dp[i][j] = grid[i][j] + dp[i+1][j];
            }else{
                 dp[i][j] = grid[i][j] + Math.min(dp[i+1][j],dp[i][j+1]);
        }
    }
}

print(dp[0][0]);

发表于 2020-08-11 16:35:39 回复(0)

xinxinxinxinxin

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int m ,n;
    cin>>m>>n;
    vector<vector<int>> mat(m,vector<int>(n,0));
    vector<vector<int>> dp(m,vector<int>(n,0));
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<n;j++)
            cin>>mat[i][j];
    }
    dp[0][0] = mat[0][0];
    for(int i = 1;i<m;i++)
    {
        dp[i][0] = dp[i-1][0] +mat[i][0];
    }
    for(int j = 1;j<n;j++)
    {
        dp[0][j] = dp[0][j-1] + mat[0][j];
    }
    for(int i = 1;i<m;i++)
    {
        for(int j = 1;j<n;j++)
            dp[i][j] = min(dp[i-1][j] + mat[i][j] , dp[i][j-1] + mat[i][j]);
    }
    cout<<dp[m-1][n-1]<<endl;
    return 0;
}

发表于 2020-06-16 14:10:22 回复(0)

Kaitle

#include<bits/stdc++.h>
using namespace std;
int M ,N ;
int main(){
    int a[10][10];
    cin>>M>>N;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            cin>>a[i][j];
        }
    }
    for(int i=M-1;i>=0;i--){
        for(int j=N-1;j>=0;j--){
            if(i+1<M && j+1<N)
            {
                a[i][j] += min(a[i+1][j],a[i][j+1]);
            }
            else if(i + 1< M)
            {
                a[i][j] += a[i+1][j];

            }else if(j + 1 < N)
            {
                a[i][j] += a[i][j+1];
            }
        }
    }
    cout<<a[0][0];

}

发表于 2020-04-23 16:24:54 回复(0)

牛客617387420号

import sys
class Solution:
    def func(self, rows, cols, arr):
        dp = [[0 for _ in range(cols)] for _ in range(rows)]
        dp[0][0] = arr[0][0]
        for i in range(1, cols):
            dp[0][i] = arr[0][i] + dp[0][i-1]
        for j in range(1, rows):
            dp[j][0] = arr[j][0] + dp[j-1][0]
        for row in range(1, rows):
            for col in range(1, cols):
                dp[row][col] = min(dp[row-1][col], dp[row][col-1])
        return dp[rows-1][cols-1]
        
                     
if __name__ == '__main__':
    solution = Solution()
    line1 = sys.stdin.readline().strip().split()
    rows = int(line1[0])
    cols = int(line1[1])
    arr = []
    while True:
        line = list(map(int, sys.stdin.readline().strip().split()))
        if not line:
            break
        arr.append(line)
    print(solution.func(rows, cols, arr))

发表于 2020-04-08 09:07:56 回复(0)