藍(lán)橋杯上岸每日N題第八期(全球變暖)！?。?/h2>

同步收錄 ??

藍(lán)橋杯上岸必背?。?！(第五期BFS)

大家好 我是寸鐵??

沖刺藍(lán)橋杯省一模板大全來啦 ??

藍(lán)橋杯4月8號(hào)就要開始了 ??

距離藍(lán)橋杯省賽倒數(shù)第3天 ?? ?? ??

還沒背熟模板的伙伴們背起來 ?? ?? ??

真題千千萬萬遍，藍(lán)橋省一自然現(xiàn)！ ??

日更3000里，藍(lán)橋眷顧你 ??

暴力出奇跡，打表過樣例 ??

祝大家4月8號(hào)藍(lán)橋杯上岸 ??

不清楚藍(lán)橋杯考什么的點(diǎn)點(diǎn)下方??

考點(diǎn)秘籍

想背純享模版的伙伴們點(diǎn)點(diǎn)下方??

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全(第一期)

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第二期）

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第三期）

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第四期）?。。?/h3>

想背注釋模版的伙伴們點(diǎn)點(diǎn)下方??

藍(lán)橋杯必背第一期

藍(lán)橋杯必背第二期

往期精彩回顧

藍(lán)橋杯上岸每日N題 第一期(一)?。?！

藍(lán)橋杯上岸每日N題第一期(二)?。?！

藍(lán)橋杯上岸每日N題第一期(三)?。?！

藍(lán)橋杯上岸每日N題第二期(一)！！！

藍(lán)橋杯上岸每日N題第三期(一)?。?！

藍(lán)橋杯上岸每日N題 第四期(最少刷題數(shù))！?。?/h3>

藍(lán)橋杯上岸每日N題 第五期(山)?。?！

藍(lán)橋杯上岸每日N題 第六期(求階乘)?。?！

藍(lán)橋杯上岸每日N題 第七期(小貓爬山)！??！

操作系統(tǒng)期末題庫 第九期(完結(jié))

LeetCode Hot100 刷題(第三期)

idea創(chuàng)建SpringBoot項(xiàng)目報(bào)錯(cuò)解決方案

數(shù)據(jù)庫SQL語句（期末沖刺）

想看JavaB組填空題的伙伴們點(diǎn)點(diǎn)下方 ??

填空題

競賽干貨

算法競賽字符串常用操作大全

藍(lán)橋杯上岸必刷?。?！(模擬/枚舉專題)

藍(lán)橋杯上岸必背！?。?(第三期 DP)

藍(lán)橋杯上岸必背?。?！(第四期DFS)

藍(lán)橋杯上岸必背！！！(第五期BFS)

藍(lán)橋杯上岸必背?。?！(第六期樹與圖的遍歷)

藍(lán)橋杯上岸必背?。?！(第七期 最短路算法)

藍(lán)橋杯上岸必背！??！(第八期 簡單數(shù)論)

前言

喜歡的小伙伴可以關(guān)注我，關(guān)注寸鐵，我們一起上岸4.8藍(lán)橋杯?。?！

全球變暖

考點(diǎn)：BFS+Queue

分析

其中”上下左右”四個(gè)方向上#連在一起的一片陸地組成一座島嶼。
具體來說如果一塊陸地像素與海洋相鄰(上下左右四個(gè)相鄰像素中有海洋.)，它就會(huì)被淹沒。

題目模擬(島嶼)

注：圖中有3個(gè)島嶼,上下連續(xù)區(qū)域。

題目模擬(海洋淹沒)

注：題中有一個(gè)島嶼全被淹沒

題目解讀

觀察一下：島嶼中陸地的數(shù)量和海洋的數(shù)量是統(tǒng)一的。
如果這個(gè)陸地上下左右方向只要有一個(gè)方向有.的話,就說明該陸地會(huì)被淹沒。
也就是只要我們在陸地上下左右方向中找到了一個(gè).,就說明這個(gè)陸地被淹沒。
換言之，如果說島嶼中陸地被淹沒了,就存在至少一個(gè)方向的海洋.
我們只需要統(tǒng)計(jì)島嶼的個(gè)數(shù)和海洋的個(gè)數(shù)即可。
如果海洋個(gè)數(shù)和島嶼中陸地的個(gè)數(shù)相等，則說明該島嶼已被淹沒。否則未被淹沒。

所以，關(guān)鍵在于維護(hù)海洋和島嶼中陸地的個(gè)數(shù)。

這題用BFS來處理
首先沒有點(diǎn)與點(diǎn)之間的關(guān)系，所以我們不用鄰接表來存儲(chǔ)邊和點(diǎn)的關(guān)系。
而是用隊(duì)列的方式去維護(hù)BFS一層一層往外搜，一層一層往外擴(kuò)。

那在bfs中我們還需要維護(hù)其他變量用于解決此題。
首先,我們需要去統(tǒng)計(jì)連通塊(島嶼)中陸地的個(gè)數(shù) res。
這里在隊(duì)頭元素出隊(duì)的時(shí)候，統(tǒng)計(jì)一下即可。
設(shè)定isbound來標(biāo)記是邊界的.
然后,彈出隊(duì)頭,進(jìn)行上下左右的坐標(biāo)移動(dòng),統(tǒng)計(jì)其上下左右方向是否有.
有的話，我們就將該位置的坐標(biāo)標(biāo)記上false。
最后統(tǒng)計(jì)一下每個(gè)島嶼的isbound的個(gè)數(shù)有多少個(gè)。

如果說res和isbound相等,則說明該島嶼全部淹沒。

代碼

import java.util.*;
public class Main{
    static int N=1010;
    static char g[][]=new char[N][N];
    static boolean st[][]=new boolean [N][N];
    static int dx[]= {1,0,-1,0};
    static int dy[]= {0,-1,0,1};
    static int n;
    static int cnt;
    public static void main(String []args) {
    	Scanner in=new Scanner(System.in);
    	n=in.nextInt();
    	for(int i=0;i<n;i++) {
    		char a[]=in.next().toCharArray();
    		for(int j=0;j<n;j++) {
    			g[i][j]=a[j];
    		} 		
    	}
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<n;j++) {
    			if(g[i][j]=='#'&&!st[i][j]) {
    			if(bfs(i,j))cnt++;		
    		}
    	}
    	}
    System.out.println(cnt);	
    }
    public static boolean bfs(int x,int y) {
    	Queue<pair>q=new LinkedList<>();
    	q.add(new pair(x,y));
    	int res=0;
    	int bound=0;
    	st[x][y]=true;
    	while(!q.isEmpty()) {
    		pair t=q.poll();
    		res++;
    		boolean isbound=false;
    		for(int i=0;i<4;i++) {
    			int a=t.x+dx[i];
    			int b=t.y+dy[i];
    			if(a<0||a>=n||b<0||b>=n)continue;
    			if(st[a][b])continue;
    			if(g[a][b]=='.') {
    				isbound=true;
    				continue;
    			}
    			q.add(new pair(a, b));
    			st[a][b]=true;
    		}
    	if(isbound)bound++;	
    	}
    	return res==bound;
    }
}
class pair{
	int x;
	int y;
	public pair(int x,int y) {
		this.x=x;
		this.y=y;
	}
}

? ? ?
看到這里，不妨點(diǎn)個(gè)關(guān)注 ??文章來源地址http://www.zghlxwxcb.cn/news/detail-626224.html

到了這里，關(guān)于藍(lán)橋杯上岸每日N題 第八期 (全球變暖)！?。〉奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！