做單頁網(wǎng)站怎么選產(chǎn)品免費(fèi)seo網(wǎng)站
根據(jù)并查集練習(xí) —島嶼數(shù)量的問題再次擴(kuò)展:
原題是給定一個(gè)二維數(shù)組matrix(char[][]),里面的值不是1就是0,上、下、左、右相鄰的1認(rèn)為是一片島。返回matrix中島的數(shù)量。
擴(kuò)展為:如果是中國(guó)的地圖,1表示沙礫,0表示水。這種情況下,matrix數(shù)組會(huì)非常非常大,怎么采用分治的思想來求土地(島嶼)的數(shù)量。
總的來說是進(jìn)行拆分,分別求出每一塊的土地?cái)?shù)量后,再次進(jìn)行合并。比如說:二維數(shù)組如圖所示
它是一個(gè)島,但是太大了,如何進(jìn)行拆分以及整合。
可以在中間任意位置進(jìn)行切割,此時(shí)左右兩邊互相不知道信息,分別拆分,左側(cè)可拆分出來A,B兩個(gè)島嶼,右側(cè)可拆分出來C,D,E三個(gè)島嶼,拆分的同時(shí)收集邊界信息,看那些島嶼(根據(jù)圖中顏色劃分)屬于哪個(gè)邊界。A,B,C,D,E共5個(gè)樣本而后根據(jù)邊界找parent。如果不相等,邊界union。