1034. Coloring A Border

Link

Solution

這題跟以前的DFS不太一樣 有幾個技術困難要克服:

1. 如何by pass 之前已經標記成border的 square? 使之不影響下一個判斷

2. 如何將dfs設計成在尋找border時可以自動疊帶?

以下設計是抄別人的，但它可以完美解決上述的問題，我自己寫的邏輯很亂而且很長就不放了 部過這樣的設計就會跟我習慣的DFS patern不太一樣，它將判斷要不要DFS這件事情做在呼叫DFS之前。而非DFS中。

public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        dfs(grid, r0, c0, grid[r0][c0]);
        
        //color the negative square
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] < 0) grid[i][j] = color;
            }
        }
        
        
        return grid;
    }
    
    int[][] dirs = new int[][] {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    public void dfs(int[][] grid, int r0, int c0, int colorInside){
        
        int M = grid.length;
        int N = grid[0].length;
                
        //to solve problem #1: by color the border negatively
        grid[r0][c0] = 0 - colorInside;
        int count = 0;
        for(int[] dir : dirs){
            int i = r0 + dir[0];
            int j = c0 + dir[1];
            if(i < 0 || i >= M || j < 0 || j >= N || Math.abs(grid[i][j]) != colorInside){
                continue;
            }
            count++;
            if(grid[i][j] == colorInside){
                //dfs is triggerd of if it need to do. - problem #2
                 dfs(grid, i, j, colorInside);        
            }
        }
        if(count == 4){
            grid[r0][c0] = colorInside;
        }
    }