# 1034. Coloring A Border
###### tags: `Leetcode` `FaceBook` `Medium` `DFS`
Link: https://leetcode.com/problems/coloring-a-border/
## 思路
DFS
一开始的想法是正常做dfs，记录所有visited的点，并用set/list记录所有border
大神解法就是类似backtracking(其实DFS就是backtracking)，先把visited的点标成原来的值的相反数，然后做完dfs之后，检查它是不是border，如果不是的话，改成原来的颜色值
backtracking(recursive dfs)和用stack做dfs的区别就在于backtracking访问完这个点之后，还可以继续对这个点做一些修改，但是用stack做，做完就做完了，所以有时可能会需要一些额外空间，但如果只是需要记visited的话，两种方法的空间占用没太大差别，所以无所谓
## Code

class Solution {
    int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        dfs(grid, row, col, grid[row][col]);
        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;
    }
    public void dfs(int[][] grid, int r, int c, int originColor){
        if(r<0 || r>= grid.length || c<0 || c>= grid[0].length || grid[r][c]!=originColor) return;
        grid[r][c] = -originColor;
        for(int i = 0; i < directions.length;i++){
            int newr = r+directions[i][0];
            int newc = c+directions[i][1];
            dfs(grid, newr, newc, originColor);
        }
        if(r>0 && r<grid.length-1 && c>0 && c<grid[0].length-1 && Math.abs(grid[r-1][c])==originColor && Math.abs(grid[r+1][c])==originColor && Math.abs(grid[r][c+1])==originColor && Math.abs(grid[r][c-1])==originColor){
            grid[r][c] = originColor;
        }
    }
}