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


jamil130011@gmail.com (許恩嘉)

學校 : 不指定學校
編號 : 249076
來源 : [1.174.49.241]
最後登入時間 ：
2023-11-09 17:27:49
m372. 3. 搬家 -- 2023年10月APCS | From: [61.227.93.56] | 發表日期 : 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 (許恩嘉)

學校 : 不指定學校
編號 : 249076
來源 : [1.174.49.241]
最後登入時間 ：
2023-11-09 17:27:49
m372. 3. 搬家 -- 2023年10月APCS | From: [61.227.93.56] | 發表日期 : 2023-10-25 21:39
宣告方式參考:用智慧指標配置一個陣列，每個陣列都是一個std::string
 
不小心寫錯字了
每個陣列都是一個std::string
每個陣列元素都是一個std::string
順便一提，要使用std::unique_ptr需引入標頭檔<memory>



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


k034006 (Sine Wu)

學校 : 高雄市立高雄高級中學
編號 : 46921
來源 : [180.217.135.99]
最後登入時間 ：
2024-09-07 23:27:34
m372. 3. 搬家 -- 2023年10月APCS | From: [180.217.135.99] | 發表日期 : 2024-09-07 23:29
 
解題思路:用一個二維陣列儲存所有水管隸屬的連通塊，再統計最大的連通塊。
用巢狀迴圈歷遍所有水管，由左至右，由上而下，檢查水管是否與上方或左方連通，若有連通，則這個水管與上或左是同一個連通塊，如果與上和左皆有連通，則合併兩個連通塊為同一個。否則這個水管屬於一個新的連通塊
巢狀迴圈結束後，我們就能得到下水道的連通塊地圖，再統計最大的連通塊就可以了
 
1.使用string陣列來儲存下水道地圖(如果你要用char map[500][500];也不是不行，這大約會消耗堆疊空間的1/4少一些。或是宣告為全域變數(全域變數不位於堆疊上))
宣告方式參考:用智慧指標配置一個陣列，每個陣列都是一個std::string
std::unique_ptr map(new std::string[n]);//用智慧指標配置一個長度為n的std::string動態陣列。關於智慧指標，我也不是很了解，但反正只要知道這樣可以宣告一個動態陣列就可以了。
2.使用一個二維陣列儲存各個的水管隸屬的連通塊
宣告方式參考:用智慧指標配置一個(偽)二維動態陣列，存取時使用(i*m+j)的方式來計算索引值。
std::unique_ptr 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中出現最多次的數字出現的次數，即可得到解答。

本質上就是這個XD https://oi-wiki.org/ds/dsu/

 
ZeroJudge Forum