1034. 边界着色（JAVA）

1034. 边界着色

1.采用BFS或DFS即可。
2.和传统的找联通不一样，本题要求对边界上色，即BFS或DFS均需要保留上一次的坐标，因为判断(x,y)是不是边界需要根据(x±1,y±1)判断，倘若(x±1,y±1)判定"成功"，则对(x,y)着色，这就是本题的最大不同。
3.本题我的BFS貌似存在重复上色现象，即有的边界可能被上色多次，故不可以使用取反值进行特殊标记，找到了直接在grid里修改即可。

1.DFS（感觉比BFS容易）

class Solution {public int[][] grid;public boolean[][] vis;public int orginal;public int m,n,color;public int[][] colorBorder(int[][] grid, int row, int col, int color) {m = grid.length;n=grid[0].length;vis= new boolean[m][n];this.grid=grid;this.color=color;orginal=grid[row][col];func(row,col,0,0);return grid;}public void func(int row,int col , int rp , int cp){if((row>=0 && row<m) && (col>=0 && col<n)){if(!vis[row][col]){if(grid[row][col]==orginal){vis[row][col]=true;func(row-1,col,row,col);func(row+1,col,row,col);func(row,col-1,row,col);func(row,col+1,row,col);}else{grid[rp][cp]=color;}}}else{grid[rp][cp]=color;}} 
}

2.BFS

class Solution {public int[][] grid;public boolean[][] vis;public Deque<int[]> q;public int m,n,color,orginal;public int[][] colorBorder(int[][] grid, int row, int col, int color) {m = grid.length;q=new ArrayDeque<>();           //Java 使用ArrayDeque模拟queue,基础操作 isEmpty(),poll()n=grid[0].length;vis= new boolean[m][n];         //布尔数组默认为False;this.grid=grid;this.color=color;orginal=grid[row][col];int[][] dir={{0,-1},{0,1},{1,0},{-1,0}};q.offer(new int[]{row,col});vis[row][col]=true;while(!q.isEmpty()){int[] res=q.poll();int x=res[0],y=res[1];for(int[] i: dir){int nx=x+i[0];int ny=y+i[1];if((0<=nx && nx<m)&& (0<=ny && ny<n)){if(!vis[nx][ny]){            if(grid[nx][ny]==orginal){vis[nx][ny]=true;q.offer(new int[]{nx,ny});}else{grid[x][y]=color;}}}else{grid[x][y]=color;}}}return grid;}}