搜索探讨2

题目链接：https://leetcode-cn.com/problems/coloring-a-border/
题目详情：

解题要点：

• 从一个点遍历整个连通量
• 将连通量的边界设置为其他颜色

dfs解法：从给定点开始遍历，借助标记数组 visited 来实现连通量的遍历。然后对连通量中的每一个点，加个判断（判断是否为边界）就完成任务了

class Solution {
    List<int []> list;
    boolean[][] visited;
    int n, m;
    int originColor;
    //判断当前连通量的点是否为边界点
    boolean judge(int[][] grid, int row, int col){
        if(row == 0 || row == n-1){
            return true;
        }
        if(col == 0 || col == m-1){
            return true;
        }
        if(row -1 >= 0){
            if(grid[row][col] != grid[row-1][col]){
                return true;
            }
        }
        if(col + 1 < m) {
            if (grid[row][col] != grid[row][col + 1]) {
                return true;
            }
        }
        if(row + 1 < n){
            if(grid[row][col] != grid[row+1][col]){
                return true;
            }
        }
        if(col - 1 >= 0){
            if(grid[row][col] != grid[row][col-1]){
                return true;
            }
        }
        return false;
    }
    void helper(int[][] grid, int row, int col, int color){
        //防止下标越界
        if(row < 0 || row >= n || col < 0 || col >=m){
            return;
        }
        //判断当前遍历到的点是否属于同一个连通量(题目给定点的连通量)
        if(grid[row][col] != originColor){
            return;
        }
        //防止在遍历连通量时产生死循环
        if(visited[row][col]){
            return;
        }
        //标记当前点已经访问
        visited[row][col] = true;
        //加个判断，如果是边界点，记录该点的坐标
        //如果把这个判断取出，其实就是dfs遍历连通量的模板
        if(judge(grid, row, col))
            list.add(new int[]{row, col});
        //对 上、右、下、左 四个方向进行搜索
        helper(grid, row-1, col, color);
        helper(grid, row, col+1, color);
        helper(grid, row+1, col, color);
        helper(grid, row, col-1, color);
    }
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        n = grid.length;
        m = grid[0].length;
        visited = new boolean[n][m];
        list = new ArrayList<>();
        originColor = grid[row][col];
        helper(grid, row, col, color);
        //那些为边界点的坐标，在grid中赋值，完成题目要求
        for(int[] dir : list){
            int x = dir[0];
            int y = dir[1];
            grid[x][y] = color;
        }
        return grid;
    }
}

时间复杂度：O(m n)。
空间复杂度：O(m n)。

bfs解法：从给定点逐层往外扩散，还是搜索四个方向，注意：bfs同样需要标记数组来防止元素多次访问

class Solution {
    int n, m;
    boolean judge(int[][] grid, int row, int col){
        if(row < 0 || row >= n || col < 0 || col >= m){
            return false;
        }
        if(row == 0 || row == n-1){
            return true;
        }
        if(col == 0 || col == m-1){
            return true;
        }
        if(row -1 >= 0){
            if(grid[row][col] != grid[row-1][col]){
                return true;
            }
        }
        if(col + 1 < m) {
            if (grid[row][col] != grid[row][col + 1]) {
                return true;
            }
        }
        if(row + 1 < n){
            if(grid[row][col] != grid[row+1][col]){
                return true;
            }
        }
        if(col - 1 >= 0){
            if(grid[row][col] != grid[row][col-1]){
                return true;
            }
        }
        return false;
    }

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        n = grid.length;
        m = grid[0].length;

        boolean[][] visited = new boolean[n][m];
        List<int[]> list = new ArrayList<>();
        int originColor = grid[row][col];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{row, col});

        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while(!q.isEmpty()){
            int size = q.size();
            for(int k = 0; k < size; k++){
                int[] point = q.poll();
                if(judge(grid, point[0], point[1])){
                    list.add(new int[]{point[0], point[1]});
                }
                visited[point[0]][point[1]] = true;
                for(int i = 0; i < 4; i++){
                    int x = point[0] + dirs[i][0];
                    int y = point[1] + dirs[i][1];
                    if(((x >= 0 && x < n) && (y >= 0 && y < m)) && !visited[x][y] && grid[x][y] == originColor){
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
        for(int[] dir : list){
            int x = dir[0];
            int y = dir[1];
            grid[x][y] = color;
        }
        return grid;

    }
}

时间和空间复杂度与dfs相同