藍橋杯（全球變暖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]);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/549132.html
標籤：其他
下一篇：Java筆記(8) 例外和錯誤