[数据结构与算法]蓝桥杯31天冲刺 Day10

扫地机器人

链接: 扫地机器人

全球变暖

链接: 全球变暖.

贴一道力扣题，和这个相似：链接: 200. 岛屿数量.

AC代码：

class Solution {
    public int numIslands(char[][] grid) {
        int count=0;
        for(int i =0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j] == '1'){
                    count++;
                    islands(grid,i,j);
                }
            }
        }
        return count;
    }

    public void islands(char[][] grid,int i,int j){
        grid[i][j] = '0';
        int[] dx = {1,0,-1,0};
        int[] dy = {0,1,0,-1};
        for(int k =0;k<4;k++){
            int xx = i+dx[k];
            int yy = j+dy[k];
            if(xx>=0&&yy>=0&&xx<grid.length&&yy<grid[0].length){
            if(grid[xx][yy] == '1')
                islands(grid,xx,yy);
            }
        }
    }
}

相当于BFS+DFS
主要就是遇到空地‘#’就进行判断、更改

我们将k记作临近水域的空地
w记为不临近水域的空地

通过BFS判断是否有空地可以更改
通过DFS进行周围空地的更改

完整代码：

package 题库;
import java.util.*;
public class 全球变暖 {
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,-1,0,1};
	public static int n;
	public static char[][] picture;
	
	public static int island(int i,int j) {
		int res = 0;
		//判断#周围是否有水域（修改k）
		for(int k =0;k<4;k++) {
			int xx = i+dx[k];
			int yy = j+dy[k];
			if(xx<0||xx>=n||yy<0||yy>=n||picture[xx][yy]!='.')
				continue;
			picture[i][j] = 'k';
		}
		//修改w
		if(picture[i][j] !='k') {
			picture[i][j] = 'w';
			res++;
		}
		//递归修改该岛屿其他部分
		for(int k =0;k<4;k++) {
			int xx = i+dx[k];
			int yy = j+dy[k];
			if (xx < 0 || yy < 0 || xx >= n || yy >= n) {
                continue;
            }
			if(picture[xx][yy] == '#')
				res+=island(xx,yy);
		}
		return res;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int pre=0;
        int after=0;
        n = sc.nextInt();
        picture = new char[n][n];
        for(int i =0;i<n;i++) {
        	picture[i] = sc.next().toCharArray();
        }
        for(int i=0;i<n;i++) {
        	for(int j=0;j<n;j++) {
        		if(picture[i][j] == '#') {
        			pre++;
        			if(island(i,j)>0)
        				after++;
        		}
        	}
        }
        System.out.println(pre-after);
        
	}

}