最短路径变式:带障碍的网格移动
已关闭dadingPython / C++入场费 3 金币0 次提交
题目描述
给定一个 m×n 的网格,其中部分格子是障碍物(标记为 1),其余为空地(标记为 0)。从左上角 (0,0) 出发,每次只能向右或向下移动一格,求到达右下角 (m-1,n-1) 的最短路径长度。如果无法到达,输出 -1。
输入格式
第一行两个整数 m 和 n(1≤m,n≤100),接下来 m 行每行 n 个整数(0=空地,1=障碍),同行数字用空格分隔
输出格式
一个整数,表示最短路径长度,或 -1 表示不可达
输入输出样例
样例 1
输入:
3 3 0 0 0 0 1 0 0 0 0
输出:
4
样例 2
输入:
2 2 1 0 0 0
输出:
2
说明/提示
动态规划:dp[i][j] 表示到达 (i,j) 的最短路径。障碍格子 dp 为 INF。注意 m=1 或 n=1 的边界情况。