记录到深度搜索(力扣417)
class Solution {
    int row;
    int col;
    int [][]dir={
  {0,1},{0,-1},{-1,0},{0,1}};//对应坐标上下左右
    Set<String> pacificVisited=new HashSet<>();//左边太平洋去重
    Set<String> atlanticVisited=new HashSet<>();
    int [][]matrix;
    int [][]heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
     row=heights.length;
     col=row==0?0:heights[0].length;
    matrix=new int [row][col];//得到的是当前数组的具体数字
    this.heights=heights;

     //在两个海洋边缘开始遍历
     for(int i=0;i<row;i++){
         //流向左边海+10,右边+100
         dfs(i,0,10);//最左边第一排遍历
         dfs(i,col-1,100);//最右边第一排遍历
     }

     for(int j=0;j<col;j++){
         dfs(0,j,10);//最上边第一排遍历
         dfs(row-1,j,100);//最下边第一排遍历
     }

     List<List<Integer>>res=new ArrayList<>();
     for(int i=0;i<row;i++){
         for(int j=0;j<col;j++){
             if(matrix[i][j]==110){
                 res.add(List.of(i,j));
             }
         }
         return res;
     }

    }
  private void dfs(int i,int j,int offset){//offset是用来判断是否访问过
      if(!isInRange(i,j))//判断不在岛上就return
      return;

      String symbol=i+"@"+j;//作为标志,用来判断是否被访问过
      if(contains(symbol,offset)){//offset用于区分左右海?
             return;//存在就直接返回,就是访问过了就不访问了,return

      //接下来进入循环,联通
      matrix[i][j]+=offset;//如果连通就加起来得到110
      add(symbol,offset);

      for(int k=0;k<4;K++){//找到新的探索方向
        int newX=i+dir[k][0];
        int newY=j+dir[k][1];

        if(isInRange(newX,newY)&&heights[newX][newY]>=heights[i][j]){//就联通性成立,高到底
             String sym=newX+"@"+newY;
             if(contains(sym,offset))//判断是否访问过
             continue;

             dfs(newX,newY,offset);//再次遍历
        }
      }

      }
  }

  //添加到海洋
  private void add(String symbol,int offset){
      if(offset==10){//在左边海,就添加到HashSet里面
          pacificVisited.add(symbol);

      }else{
          atlanticVisited.add(symbol);
      }
  }


        //通过不同的索引知道在哪个海洋包含
    private boolean contains(String symbol,int offset){
        if(offset==10){//通过不同的索引知道在哪个海洋包含
            return pacificVisited.contains(symbol);
        }else{
            return atlanticVisited.contains(symbol);
        }
    }



    private boolean isInRange(int i,int j){//判断是否在边界的条件
    return i>=0&&j>=0&&i<row&&j<col;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-09 22:57
安徽大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议