0980. Unique Paths III¶
题目信息¶
- 题号:
0980
- 难度:
Hard
- 主题:
网格、路径计数、全覆盖访问
- 原题:
- 重点:
从唯一的起点走到唯一终点,只能上下左右移动;除障碍外的每个格子必须恰好访问一次,包括起点和终点
题目重述¶
给定整数网格 grid,其中 1 表示唯一起点,2 表示唯一终点,0 表示可行走的空格,-1 表示不能进入的障碍。
从起点开始,每一步只能向上、下、左、右移动到相邻格。请统计有多少条路径最终到达终点,并且路径必须把所有非障碍格子恰好访问一次;不能重复进入任何格子,也不能在尚有未访问空格时提前结束。
1 <= grid.length, grid[i].length <= 20,格子总数不超过 20,输入恰好包含一个起点和一个终点。
自建示例¶
单行网格只有一种全覆盖路径:
输入:grid = [[1,0,0,2]]
输出:1
解释:只能从左向右依次经过两个空格并到达终点,所有非障碍格都恰好访问一次。
二维网格无法在终点前访问全部格子:
输入:grid = [[1,0],[0,2]]
输出:0
解释:从起点先访问任一空格后都会紧接着到达终点,另一空格尚未访问;又不能重复经过起点,因此不存在合法路径。