首页 > itarticle > leetcode1034

leetcode1034

admin 11月 12, 2020 0

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

主要是连通分量的边界判定条件,向外扩展,根据是否是边界确定是否染色,已扫描的标记一下,防止重复扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
class Solution {
    public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] f= new boolean[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                f[i][j] = false;
            }
        int t =  grid[r0][c0];
        dfs(grid,f,r0,c0,color,t);
        return grid;
    }
    
    private void dfs(int[][] grid, boolean[][] f, int r, int c, int color,int old){
        f[r][c] = true;
        if (r-1>=0 &&  grid[r-1][c]==old && f[r-1][c]==false){
            dfs(grid,f,r-1,c,color,old); 
        }
        
        if (r+1<grid.length && f[r+1][c]==false &&  grid[r+1][c]==old){
            dfs(grid,f,r+1,c,color,old);
        }
        if (c-1>=0 && f[r][c-1]==false &&  grid[r][c-1]==old){
            dfs(grid,f,r,c-1,color,old);
        }
        if (c+1<grid[0].length && f[r][c+1]==false &&  grid[r][c+1]==old){
            dfs(grid,f,r,c+1,color,old);
        }
        
        boolean t = false;
        if (r-1>=0 && f[r-1][c]==false){
            t=true;
        }
        if (r+1<grid.length && f[r+1][c]==false){
            t=true;
        }
        if (c-1>=0 && f[r][c-1]==false ){
           t=true;
        }
        if (c+1<grid[0].length && f[r][c+1]==false){
            t=true;
        }
        if (c==grid[0].length-1||c==0){
            t = true;
        }
        if (r==grid.length -1||r==0){
            t = true;
        }
    
        
        if (t){
            grid[r][c] = color;
        }
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能