#38100: C++ 不使用BFS/DFS的超快(7ms)超簡單(沒用到複雜的演算法)作法


jamil130011@gmail.com (許恩嘉)

School : No School
ID : 249076
IP address : [1.174.49.241]
Last Login :
2023-11-09 17:27:49
m372. 3. 搬家 -- 2023年10月APCS | From: [61.227.93.56] | Post Date : 2023-10-25 21:31

 
解題思路:用一個二維陣列儲存所有水管隸屬的連通塊,再統計最大的連通塊。
用巢狀迴圈歷遍所有水管,由左至右,由上而下,檢查水管是否與上方或左方連通,若有連通,則這個水管與上或左是同一個連通塊,如果與上和左皆有連通,則合併兩個連通塊為同一個。否則這個水管屬於一個新的連通塊
巢狀迴圈結束後,我們就能得到下水道的連通塊地圖,再統計最大的連通塊就可以了
 
1.使用string陣列來儲存下水道地圖(如果你要用char map[500][500];也不是不行,這大約會消耗堆疊空間的1/4少一些。或是宣告為全域變數(全域變數不位於堆疊上))
宣告方式參考:用智慧指標配置一個陣列,每個陣列都是一個std::string
std::unique_ptr<std::string[]> map(new std::string[n]);//用智慧指標配置一個長度為n的std::string動態陣列。關於智慧指標,我也不是很了解,但反正只要知道這樣可以宣告一個動態陣列就可以了。
2.使用一個二維陣列儲存各個的水管隸屬的連通塊
宣告方式參考:用智慧指標配置一個(偽)二維動態陣列,存取時使用(i*m+j)的方式來計算索引值。
std::unique_ptr<int[]> array(new int[n * m]);
3.使用巢狀迴圈歷遍下水道地圖(陣列map)的每一個字元,檢查是否有與上方或左方連通,若有連通,則在array上記錄其屬於同一連通塊(若同時連通上與左,會需要將連通塊合併,合併連通塊時須注意不要用錯方法造成TLE),若沒有連接,紀錄其為一個新的連通塊。若沒有該區域沒有水管(map[i][j]=='0'),在array上記錄為-1
4.此時array中應已記錄了下水道中的連通狀況,輸出一下檢查有沒有錯誤
範例1:
0/0/0/0/
0/1/2/0/
0/0/0/0/
範例2:
-1/0/0/-1/-1/-1/-1/
0/0/0/-1/-1/-1/-1/
0/0/2/-1/-1/3/3/
0/0/-1/4/4/3/3/
斜線是輸出時加上去的
5.統計array中出現最多次的數字出現的次數,即可得到解答。
 
#38101: Re: C++ 不使用BFS/DFS的超快(7ms)超簡單(沒用到複雜的演算法)作法


jamil130011@gmail.com (許恩嘉)

School : No School
ID : 249076
IP address : [1.174.49.241]
Last Login :
2023-11-09 17:27:49
m372. 3. 搬家 -- 2023年10月APCS | From: [61.227.93.56] | Post Date : 2023-10-25 21:39

宣告方式參考:用智慧指標配置一個陣列,每個陣列都是一個std::string
 
不小心寫錯字了
每個陣列都是一個std::string
每個陣列元素都是一個std::string
順便一提,要使用std::unique_ptr需引入標頭檔<memory>



 
ZeroJudge Forum