959. Regions Cut By Slashes

Link

Solution

這題最難的地方是想到怎麼把 string[] grid轉換成 我們熟悉的int[][] gird,

這關過後就是熟悉的DFS找island的類型。

  public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        int[][] newGrid = new int[N*3][N*3]; // trickey
        //transform gird to newGrid
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(grid[i].charAt(j) == '/'){
                    newGrid[i*3][j*3+2] = newGrid[i*3+1][j*3+1] = newGrid[i*3+2][j*3] = 1;
                }
                else if( grid[i].charAt(j) == '\\'){
                    newGrid[i*3][j*3] = newGrid[i*3+1][j*3+1] = newGrid[i*3+2][j*3+2] = 1;
                }
            }
        }
        int ret = 0;
        for(int i = 0; i < 3*N; i++){
            for(int j = 0; j < 3*N; j++){
                if(newGrid[i][j] == 0){
                    dfs(newGrid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
    
    public void dfs(int[][] grid, int i, int j){
        
        int N = grid.length;
        if(i < 0 || j < 0 || i >= N || j >= N || grid[i][j] == 1) return;
        
        grid[i][j] = 1;
        
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }