蓝桥杯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';}//修改wif(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 stubScanner 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);}}