蓝桥杯（全球变暖dfs）

import java.util.Scanner;

/**
 * 该题使用了深度优先算法dfs用于把相连的#号当成一块大陆，并通过数组记录下有几块大陆
 * dfs算法并不难，只要对用dfs处理过后留下的aes数组和sea数组进行处理得到结果即可
 * 我的思路就是
 * 1、sea数组记录源数据，然后判断是否被淹赋‘*’号记录
 * 2、aes数组使用dfs算法把第一块大陆标记为1，第二块标记为2，以此类推
 * 3、最后假设num块大陆全部被淹，遍历sea数组如果有‘#’号则判断是第几块大陆，没有重复就使num减一
 * 4、最后输出num为最终结果
 */

public class test1 {
    static char[][] sea;//用于记录用例
    static int[][] aes;//用于记录不同的大陆，其值为不同大陆的标记
    static int n;//输入的初值
    static int num=0;//最后被淹没的大陆数量
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        sea = new char[n][n];
        aes = new int[n][n];
        //初始化sea
        for(int i=0;i<n;i++){
            sea[i] = scan.next().toCharArray();
        }
        //给aes初值全部赋0
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
              aes[i][j]=0;

        for(int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if(sea[i][j]=='#'){
                    if(aes[i][j]==0) {
                        num++;
                        dfs(i, j);//当检测到陆地就使用dfs()方法赋值
                    }
                    if(submerge(i,j))
                        sea[i][j]='*';//使用sunmerge方法判断是否会被淹没，被淹没就赋‘*’
                }
            }
        }
        //目前已知有num块陆地，使用数组land[]记录下还未被淹的陆地
        int[] land = new int[num];
        for(int i=0;i<num;i++)
            land[i]=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(sea[i][j]=='#'){//当有被还未被淹没的陆地时
                    int x=aes[i][j]-1;
                    if(land[x]!=0){//此陆地还未被记录就把land赋0，淹没的陆地数num-1
                        land[x]=0;
                        num--;
                    }
                }
            }
        System.out.println(num);
    }

    static int[] x = {0,1,0,-1};
    static int[] y = {1,0,-1,0};
    //判断是否会被淹没，淹没返回true，否则返回false
    public static boolean submerge(int a, int b){
        for(int i=0;i<4;i++){
            if(a+y[i]>=0 && a+y[i]<n && b+x[i]>=0 && b+x[i]<n && sea[a+y[i]][b+x[i]]=='.')
                return true;
        }
        return false;
    }
    //DFS深度优先，把所在的大陆通过dfs都标记上记号num如:
    /*
    sea[][]: ....   aes[][]:0000
             .##.           0110
             ....           0000
     */
    public static void dfs(int a,int b){
        aes[a][b]=num;
        for(int i=0;i<4;i++){
            if(a+y[i]>=0 && a+y[i]<n && b+x[i]>=0 && b+x[i]<n && sea[a+y[i]][b+x[i]]=='#'&&aes[a+y[i]][b+x[i]]==0)
                dfs(a+y[i],b+x[i]);
        }
    }
}

热门相关：首席的独宠新娘   薄先生，情不由己   霸皇纪   大神你人设崩了   时间都知道（唐嫣、窦骁、杨烁主演）