最短路径变式:带障碍的网格移动

已关闭
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 的边界情况。