专门教做衣服的网站,编程网站项目做哪个比较好,太原建站模板系统,分析网站优缺点文章目录 Unique Paths III 不同路径 III DFS 暴力问题描述#xff1a;分析代码DFS 暴力 Tag Unique Paths III 不同路径 III DFS 暴力
问题描述#xff1a;
在二维网格 grid 上#xff0c;有 4 种类型的方格#xff1a;
1 表示起始方格。且只有一个起始方格。 2 表示结… 文章目录 Unique Paths III 不同路径 III DFS 暴力问题描述分析代码DFS 暴力 Tag Unique Paths III 不同路径 III DFS 暴力
问题描述
在二维网格 grid 上有 4 种类型的方格
1 表示起始方格。且只有一个起始方格。 2 表示结束方格且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向上、下、左、右上行走时从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次但是一条路径中不能重复通过同一个方格。 1 g r i d . l e n g t h ∗ g r i d [ 0 ] . l e n g t h 20 1 grid.length * grid[0].length 20 1grid.length∗grid[0].length20
分析 一开始看到路径问题让我联想到了DP但是看完要求就果断放弃了。 在这样一个矩阵中从出发点S到终点E无障碍的方格必须仅过一次。 基于这个要求是无法找到合适的子问题的。 假设路径中的点X到达X时可以是4个方向而且之前的路径也无法通过子问题来得到。 但是可以知道的是到达X时走了多少步还有多少步可以走。 一个矩阵上除去障碍剩余的 空白处都是必须经过的假设这个数量为tot。
新问题就是走完tot数量恰好可以到达E的路径数。
因为不能重复经过同一个方格所以可以使用一个标记数组记录已访问的方格。
剩下的就是解决从x,y出发恰好经过left可以到达E的路径数。 到此就是利用DFS搜索来解决为了加速可以使用memo。
代码 DFS 暴力
class Solution {public int uniquePathsIII(int[][] grid) {int cnt0 0, sx -1, sy -1;for (int i 0; i grid.length; i) {for (int j 0; j grid[i].length; j) {if (grid[i][j] 0) cnt0;else if (grid[i][j] 1) { // 起点sx i;sy j;}}}return dfs(grid, sx, sy, cnt0 1); // 1 把起点也算上}private int dfs(int[][] grid, int x, int y, int left) {if (x 0 || x grid.length || y 0 || y grid[x].length || grid[x][y] 0)return 0; // 不合法if (grid[x][y] 2) // 到达终点return left 0 ? 1 : 0; // 必须访问所有的无障碍方格grid[x][y] -1; // 标记成访问过因为题目要求「不能重复通过同一个方格」int ans dfs(grid, x - 1, y, left - 1) dfs(grid, x, y - 1, left - 1) dfs(grid, x 1, y, left - 1) dfs(grid, x, y 1, left - 1);grid[x][y] 0; // 恢复现场return ans;}
}
时间复杂度 O ( 很大 ) O(很大) O(很大)
空间复杂度 O ( M N ) O(MN) O(MN)
该代码来源于 灵神大佬值得学习
Tag
Matrix
Backtracking
