Wayfair
  • OA
    • Karat
      • 811. Subdomain Visit Count
      • Ads Conversion Rate
      • Recommend Movie
      • Longest Common Continuous Subarray
      • Course Overlap
      • Halfway courses
      • Find one rectangle
      • Find all rectangles
      • Find Multiple Shapes
      • word wrap
      • word processor
      • Basic Calculator
      • Basic Calculator with parenthesis
      • 带变量计算器
      • Valid Matrix
      • nonogram
      • Node with 0 or 1 parents
      • 两个节点是否有公共祖先
      • 最远祖先
      • invalid Badge Records
      • 一小时内access多次
      • canSchedule
      • spareTime
      • sparse vector
      • sparse vector 实现add,dot和cos
      • userlogs earliest and latest access time
      • resource Access with in 5 min
      • Find Word Path in Grid
      • Find legal moves
      • 找能去的所有0区域
      • 最短路径找treasure
  • VO
    • Coding
      • Valid Palindrome
      • Add String
      • Coupon
    • System design
    • BQ
    • OOD
  • SD
  • LeetCode Tag
  • VO Onsite
Powered by GitBook
On this page
  1. OA
  2. Karat

找能去的所有0区域

给一个二维matrix,-1代表墙,0代表路。问给定一个起点坐标为0,是否能到达所有的0。

public class AllReachableZero {
    

    public boolean findAllReachableZero(int[][] matrix, int x, int y)
    {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        dfs(matrix, x, y, visited);
        for(int i = 0; i< matrix.length; i++)
        {
            for(int j = 0; j< matrix[0].length; j++)
            {
                if(!visited[i][j] && matrix[i][j] == 0)
                {
                    return false;
                }
            }
        }
        return true;
    }

    public void dfs(int[][] matrix, int i, int j, boolean[][] visited)
    {
        if(!isBound(matrix, i, j) || visited[i][j] || matrix[i][j] == -1 || matrix[i][j] == 1)
        {
            return;
        }

        visited[i][j] = true;
        matrix[i][j] = 1;
        dfs(matrix, i-1, j, visited);
        dfs(matrix, i+1, j, visited);
        dfs(matrix, i, j-1, visited);
        dfs(matrix, i, j+1, visited);
    }

    public boolean isBound(int[][] matrix, int i, int j)
    {
        return i>=0 && i<matrix.length && j>=0 && j<matrix[0].length;
    }
}
PreviousFind legal movesNext最短路径找treasure

Last updated 3 years ago