力扣-图论-17【算法学习day.67】
前言
###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.检查网格中是否存在有效路径
题目链接:1391. 检查网格中是否存在有效路径 - 力扣(LeetCode)分析:就是dfs,判断条件比较繁琐
代码:
class Solution {
int[][] grid;
int n,m;
int[][] flag;
boolean ans = false;
public boolean hasValidPath(int[][] grid) {
this.grid = grid;
n = grid.length;
m = grid[0].length;
flag = new int[n][m];
flag[0][0] = 1;
recursion(0,0);
return ans;
}
public void recursion(int x,int y){
// System.out.println(x+" "+y);
if(x==n-1&&y==m-1){
ans = true;
return;
}
if(x+1<n&&flag[x+1][y]==0){
flag[x+1][y] = 1;
if(grid[x][y]==2&&grid[x+1][y]==2){
recursion(x+1,y);
}
if(grid[x][y]==2&&(grid[x+1][y]==5||grid[x+1][y]==6)){
recursion(x+1,y);
}
if((grid[x][y]==3||grid[x][y]==4)&&grid[x+1][y]==2){
recursion(x+1,y);
}
if((grid[x][y]==3||grid[x][y]==4)&&(grid[x+1][y]==5||grid[x+1][y]==6)){
recursion(x+1,y);
}
flag[x+1][y] = 0;
}
if(x-1>=0&&flag[x-1][y]==0){
flag[x-1][y] = 1;
if(grid[x][y]==2&&grid[x-1][y]==2){
recursion(x-1,y);
}
if((grid[x][y]==5||grid[x][y]==6)&&(grid[x-1][y]==3||grid[x-1][y]==4)){
recursion(x-1,y);
}
if((grid[x][y]==5||grid[x][y]==6)&&grid[x-1][y]==2){
recursion(x-1,y);
}
if(grid[x][y]==2&&(grid[x-1][y]==3||grid[x-1][y]==4)){
recursion(x-1,y);
}
flag[x-1][y] = 0;
}
if(y+1<m&&flag[x][y+1]==0){
flag[x][y+1] = 1;
if(grid[x][y]==1&&grid[x][y+1]==1){
recursion(x,y+1);
}
if(grid[x][y]==1&&(grid[x][y+1]==3||grid[x][y+1]==5)){
recursion(x,y+1);
}
if((grid[x][y]==4||grid[x][y]==6)&&grid[x][y+1]==1){
recursion(x,y+1);
}
if((grid[x][y]==4||grid[x][y]==6)&&(grid[x][y+1]==3||grid[x][y+1]==5)){
recursion(x,y+1);
}
flag[x][y+1] = 0;
}
if(y-1>=0&&flag[x][y-1]==0){
flag[x][y-1]=1;
if(grid[x][y]==1&&grid[x][y-1]==1){
recursion(x,y-1);
}
if(grid[x][y]==1&&(grid[x][y-1]==4||grid[x][y-1]==6)){
recursion(x,y-1);
}
if((grid[x][y]==3||grid[x][y]==5)&&grid[x][y-1]==1){
recursion(x,y-1);
}
if((grid[x][y]==3||grid[x][y]==5)&&(grid[x][y-1]==4||grid[x][y-1]==6)){
recursion(x,y-1);
}
flag[x][y-1] = 0;
}
}
}
2.太平洋大西洋水流问题
题目链接:417. 太平洋大西洋水流问题 - 力扣(LeetCode)
题面:
分析:dfs,用两个变量来判断是否既能流入太平洋又能流入大西洋,复杂度较高
代码:
class Solution {
int[][] heights;
int n,m;
int[][] flag;
int flag2 = 0;
int flag3 = 0;
List<Integer> list;
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> pacificAtlantic(int[][] heights) {
this.heights = heights;
n = heights.length;
m = heights[0].length;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
flag2 = 0;
flag3 = 0;
list = new ArrayList<>();
flag = new int[n][m];
flag[i][j] = 1;
recursion(i,j);
if(flag2==1&&flag3==1){
list.add(i);
list.add(j);
ans.add(list);
}
}
}
return ans;
}
public void recursion(int x,int y){
if(x==0||y==0)flag2 = 1;
if(x==n-1||y==m-1)flag3 = 1;
if(flag2==1&&flag3==1)return;
if(x+1<n&&heights[x+1][y]<=heights[x][y]&&flag[x+1][y]==0){
flag[x+1][y] = 1;
recursion(x+1,y);
flag[x+1][y] = 0;
}
if(x-1>=0&&heights[x-1][y]<=heights[x][y]&&flag[x-1][y]==0){
flag[x-1][y] = 1;
recursion(x-1,y);
flag[x-1][y] = 0;
}
if(y+1<m&&heights[x][y+1]<=heights[x][y]&&flag[x][y+1]==0){
flag[x][y+1] = 1;
recursion(x,y+1);
flag[x][y+1] = 0;
}
if(y-1>=0&&heights[x][y-1]<=heights[x][y]&&flag[x][y-1]==0){
flag[x][y-1] = 1;
recursion(x,y-1);
flag[x][y-1] = 0;
}
}
}
后言
上面是力扣图论专题,下一篇是其他的习题,希望有所帮助,一同进步,共勉!