当前位置:网站首页>980. 不同路径 III DFS
980. 不同路径 III DFS
2022-07-07 00:25:00 【钰娘娘】
980. 不同路径 III
在二维网格
grid
上,有 4 种类型的方格:
1
表示起始方格。且只有一个起始方格。2
表示结束方格,且只有一个结束方格。0
表示我们可以走过的空方格。-1
表示我们无法跨越的障碍。返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次,但是一条路径中不能重复通过同一个方格。
示例 1:
输入:[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出:2 解释:我们有以下两条路径: 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)示例 2:
输入:[[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出:4 解释:我们有以下四条路径: 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3) 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3) 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)示例 3:
输入:[[0,1],[2,0]] 输出:0 解释: 没有一条路能完全穿过每一个空的方格一次。 请注意,起始和结束方格可以位于网格中的任意位置。提示:
1 <= grid.length * grid[0].length <= 20
做题结果
成功
方法:DFS
1. 找到起点位置,终点位置,空地数
2. 从起点出发依次尝试每条路径,占用过的空地修改为1,尝试之后还原回0
class Solution {
public int uniquePathsIII(int[][] grid) {
int[] start = null;
int[] end = null;
int m = grid.length;
int n = grid[0].length;
int empty = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
switch(grid[i][j]){
case 0: {++empty; break;}
case 1: start = new int[]{i,j}; break;
case 2: end = new int[]{i,j}; break;
}
}
}
dfs(start,end,grid,empty);
return ans;
}
int ans = 0;
int[] directions = new int[]{0,1,0,-1,0};
private void dfs(int[] start, int[] end,int[][]grid,int empty){
int m = grid.length;
int n = grid[0].length;
for(int i = 0; i < 4; i++){
int x = start[0]+directions[i];
int y = start[1]+directions[i+1];
if(x>=0&&x<m&&y>=0&&y<n){
if(empty == 0){
if(x==end[0]&&y==end[1])++ans;
}else{
if(grid[x][y]==0){
grid[x][y]=1;
dfs(new int[]{x,y},end,grid,empty-1);
grid[x][y]=0;
}
}
}
}
}
}
边栏推荐
猜你喜欢
nVisual网络可视化
随机生成session_id
Forkjoin is the most comprehensive and detailed explanation (from principle design to use diagram)
What is message queuing?
集群、分布式、微服務的區別和介紹
Getting started with DES encryption
Preliminary practice of niuke.com (9)
Introduction to distributed transactions
What are the common message queues?
集群、分布式、微服务的区别和介绍
随机推荐
Go 语言的 Context 详解
Paper reading [semantic tag enlarged xlnv model for video captioning]
得物客服一站式工作台卡顿优化之路
Get the way to optimize the one-stop worktable of customer service
Harmonyos practice - Introduction to development, analysis of atomized services
【日常训练--腾讯精选50】235. 二叉搜索树的最近公共祖先
毕业之后才知道的——知网查重原理以及降重举例
C nullable type
4. 对象映射 - Mapping.Mapster
集群、分布式、微服務的區別和介紹
Taobao commodity details page API interface, Taobao commodity list API interface, Taobao commodity sales API interface, Taobao app details API interface, Taobao details API interface
论文阅读【Sensor-Augmented Egocentric-Video Captioning with Dynamic Modal Attention】
【日常训练--腾讯精选50】292. Nim 游戏
Leakage relay jd1-100
5阶多项式轨迹
《HarmonyOS实战—入门到开发,浅析原子化服务》
bat 批示处理详解
Preliminary practice of niuke.com (9)
成为资深IC设计工程师的十个阶段,现在的你在哪个阶段 ?
淘宝店铺发布API接口(新),淘宝oAuth2.0店铺商品API接口,淘宝商品发布API接口,淘宝商品上架API接口,一整套发布上架店铺接口对接分享