当前位置:网站首页>980. Different path III DFS
980. Different path III DFS
2022-07-07 05:53:00 【Empress Yu】
980. Different paths III
On a two-dimensional grid
grid
On , Yes 4 Two types of squares :
1
Represents the starting square . And there's only one starting square .2
Indicates the end square , And there's only one end square .0
An empty square that we can walk through .-1
It's an obstacle we can't cross .Return in four directions ( On 、 Next 、 Left 、 Right ) When you go up , The number of different paths from the start square to the end square .
Every barrier free square has to pass once , But you can't go through the same grid repeatedly in a path .
Example 1:
Input :[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] Output :2 explain : We have two paths : 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)Example 2:
Input :[[1,0,0,0],[0,0,0,0],[0,0,0,2]] Output :4 explain : We have four paths : 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)Example 3:
Input :[[0,1],[2,0]] Output :0 explain : There is no way to go through every empty square completely once . Please note that , The start and end squares can be located anywhere in the grid .Tips :
1 <= grid.length * grid[0].length <= 20
The result of doing the question
success
Method :DFS
1. Find the starting point , Final position , Number of open spaces
2. Start from the starting point and try each path in turn , The occupied space is modified to 1, Try to revert back to 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;
}
}
}
}
}
}
边栏推荐
- Flink SQL realizes reading and writing redis and dynamically generates hset key
- Get the way to optimize the one-stop worktable of customer service
- ForkJoin最全详解(从原理设计到使用图解)
- Lombok plug-in
- Determine whether the file is a DICOM file
- 分布式全局ID生成方案
- Question 102: sequence traversal of binary tree
- Interview skills of software testing
- Input of native applet switches between text and password types
- 原生小程序 之 input切换 text与password类型
猜你喜欢
分布式全局ID生成方案
Five core elements of architecture design
如果不知道这4种缓存模式,敢说懂缓存吗?
数字IC面试总结(大厂面试经验分享)
消息队列:消息积压如何处理?
Opensergo is about to release v1alpha1, which will enrich the service governance capabilities of the full link heterogeneous architecture
判断文件是否为DICOM文件
Paper reading [semantic tag enlarged xlnv model for video captioning]
Reptile exercises (III)
Common skills and understanding of SQL optimization
随机推荐
Sidecar mode
Why does the data center need a set of infrastructure visual management system
What EDA companies are there in China?
分布式事务解决方案之TCC
SAP ABAP BDC (batch data communication) -018
TCC of distributed transaction solutions
消息队列:如何确保消息不会丢失
AI人脸编辑让Lena微笑
拼多多新店如何获取免费流量,需要从哪些环节去优化,才能有效提升店内免费流量
Nodejs get client IP
What is make makefile cmake qmake and what is the difference?
老板总问我进展,是不信任我吗?(你觉得呢)
Message queue: how to deal with message backlog?
得物客服一站式工作台卡顿优化之路
Interview skills of software testing
[solved] record an error in easyexcel [when reading the XLS file, no error will be reported when reading the whole table, and an error will be reported when reading the specified sheet name]
Flink SQL realizes reading and writing redis and dynamically generates hset key
如何提高网站权重
What are the common message queues?
Digital IC interview summary (interview experience sharing of large manufacturers)