【每日一题Day285】LC980不同路径 III | 回溯

简介: 【每日一题Day285】LC980不同路径 III | 回溯

不同路径 III【LC980】

在二维网格 grid 上,有 4 种类型的方格:

  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格,且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍。
  • 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目**。**

每一个无障碍方格都要通过一次,但是一条路径中不能重复通过同一个方格

  • 思路从起点出发,寻找经过所有空格到达终点的路径个数
  • 首先遍历一遍矩阵,找到起点位置、终点位置以及空格数量
  • 然后通过dfs+回溯的方式,寻找有效路径,为了防止重复遍历,还需要使用visit数组记录每个结点的访问状态

实现

  • loc(当前位置)
  • left(当前剩余的空格数量)
  • 全局变量:gridvisit
  • 返回值 int:从当前位置当终点的路径个数
  • 回溯函数终止条件
  • 到达终点时返回,如果剩余空格个数为0,返回1;反之,返回0
  • 首先判断当前位置是否访问过【记忆化,优化不明显】
  • 然后判断是否到达终点
  • 再向四个方向进行移动,需要判断坐标是否合法、是否被访问过、是否是障碍物
class Solution {
    int m, n;
    boolean[][] visit;
    int[][] grid;
    int[] dir = {0, 1, 0, -1, 0};
    int[] end;
    int[][] dp;
    public int uniquePathsIII(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.visit = new boolean[m][n];
        this.grid = grid;
        int[] start = new int[2];
        this.end = new int[2];
        this.dp = new int[m][n];
        int total = 0;
        for (int i = 0; i < m; i++){
            Arrays.fill(dp[i], -1);
            for (int j = 0; j < n; j++){
                if (grid[i][j] == 1){
                    start[0] = i;
                    start[1] = j;
                }else if (grid[i][j] == 2){
                    end[0] = i;
                    end[1] = j;
                    total++;
                }else if (grid[i][j] == 0){
                    total++;
                }
            }
        }
        visit[start[0]][start[1]] = true;
        return dfs(start, total);
    }
    public int dfs(int[] loc, int left){
        if (dp[loc[0]][loc[1]] != -1) return dp[loc[0]][loc[1]];
        if (loc[0] == end[0] && loc[1] == end[1]){
            if (left == 0){
                return 1;
            }else{
                return 0;
            }
        }
        int res = 0;        
        for (int i = 0; i < 4; i++){
            int[] u = {loc[0] + dir[i], loc[1] + dir[i + 1]};
            if (u[0] >= 0 && u[0] < m && u[1] >= 0 && u[1] < n && !visit[u[0]][u[1]] && grid[u[0]][u[1]] != -1){
                visit[u[0]][u[1]] = true;
                res += dfs(u, left - 1);
                visit[u[0]][u[1]] = false;
            }
        }
        return res;
    }
}

image.png

目录
相关文章
|
7月前
【每日一题Day335】LC1993树上的操作 | dfs
【每日一题Day335】LC1993树上的操作 | dfs
46 0
|
7月前
【每日一题Day214】LC1080根到叶路径上的不足节点 | 递归
【每日一题Day214】LC1080根到叶路径上的不足节点 | 递归
51 0
|
7月前
|
人工智能 BI
【每日一题Day232】LC2699修改图中的边权 |最短路径
【每日一题Day232】LC2699修改图中的边权 |最短路径
39 0
|
7月前
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
42 0
|
7月前
【每日一题Day212】LC1373二叉搜索子树的最大键值和 | dfs+树形dp
【每日一题Day212】LC1373二叉搜索子树的最大键值和 | dfs+树形dp
29 0
|
7月前
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
49 0
|
7月前
|
机器学习/深度学习 存储
【每日一题Day112】LC1233删除子文件夹 | 排序 字典树
【每日一题Day112】LC1233删除子文件夹 | 排序 字典树
44 1
|
7月前
【每日一题Day160】LC1092最短公共超序列 | 动态规划
【每日一题Day160】LC1092最短公共超序列 | 动态规划
41 0
【每日一题Day160】LC1092最短公共超序列 | 动态规划
|
7月前
【每日一题Day138】LC1653使字符串平衡的最少删除次数 | 前后缀 动态规划
【每日一题Day138】LC1653使字符串平衡的最少删除次数 | 前后缀 动态规划
60 0
|
7月前
【每日一题Day151】LC1625执行操作后字典序最小的字符串 | BFS
【每日一题Day151】LC1625执行操作后字典序最小的字符串 | BFS
38 0