#39467: C++遞迴解法
思路:建立一個二維陣列(圖)，標記所有走過的點，當遇到不是0的水管，且在圖上對應位置的點未被標記時，藉由一個函式replace()在圖上標記該水管，並檢查上下左右是否有未被標記且與此水管相通的水管。如果有，則以新的座標呼叫replace函式(遞迴)，replace()函式負責回傳這次函數呼叫時標記的水管數目，再將該回傳值與當前最大值比較，取較大者。
但是如果單純這樣寫在最後一比測資將會因遞迴過深而堆疊溢位。由於大多數的水管只有兩頭，一進一出，因此我們可以利用尾遞迴的概念進行優化。
下方的兩個replace函數的功能是一樣的，差別只在第一個replace()沒有尾遞迴優化，第二個Replace()在只有一個方向連出去時會用更新參數並用goto回到函數開頭，減少重複的函數呼叫，達成類似尾遞迴優化的效果，顯著減少遞迴深度。
唯一的缺點就是如果水管全都是X(有兩個方向可連出去)的話作用有限，不過似乎並沒有這樣的測資。
#include<iostream>
#include<memory> //為了使用智慧指標std::unique_ptr
#include<vector>
int n = 0, m = 0; //宣告為全域變數，這樣就可以在直接在函式中使用了(偷懶作法)
char map[500][501] = {};
struct WSAD{
bool w;
bool s;
bool a;
bool d;
inline int sum() {
return w + s + a + d;
}
} wsad[89]{};
int Replace(const int New, int i, int j, int* ij);
int main() {
wsad['F'] = { 0,1,0,1 };
wsad['H'] = { 0,0,1,1 };
wsad['7'] = { 0,1,1,0 };
wsad['I'] = { 1,1,0,0 };
wsad['X'] = { 1,1,1,1 };
wsad['L'] = { 1,0,0,1 };
wsad['J'] = { 1,0,1,0 };
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n >> m;
for (int i = 0; i < n; i++) {
std::cin >> map[i];
}
//二維陣列array儲存了每個水管隸屬的連通塊，數字相同的水管皆連接在一起
std::unique_ptr<int[]> array_(new int[n * m] {});//用智慧指標配置一個(偽)二維動態陣列，存取時使用(i*m+j)的方式來計算索引值。
int* array = array_.get();
int flag = 0;
int Max=0; //這個陣列用於統計各連通塊的大小
for (int i = 0; i < n; i++) {//巢狀迴圈，用於歷遍map中的所有元素
for (int j = 0; j < m; j++) {
if (map[i][j] == '0' or array[i * m + j] != 0) { continue; }
Max = std::max(Replace(++flag, i, j, array + (i * m + j)), Max);
}
}
//這段程式碼可以輸出下水道中水管連接的狀況，你可以試著執行看看
//std::cout << '\n';
//for (int i = 0; i < n * m; i++) {
// std::cout << array[i] << '/';
// if ((i + 1) % m == 0) { std::cout << '\n'; }
//}
//std::cout << '\n';
std::cout << Max;
return 0;
}
int replace(const int New, const int i, const int j, int* ij) {
int count = 1;
*ij = New;
if (wsad[map[i][j]].w and i > 0 and ij[-m] == 0 and wsad[map[i - 1][j]].s) {
count += replace(New, i - 1, j, ij - m);
}
if (wsad[map[i][j]].s and i < n - 1 and ij[m] == 0 and wsad[map[i + 1][j]].w) {
count += replace(New, i + 1, j, ij + m);
}
if (wsad[map[i][j]].a and j > 0 and ij[-1] == 0 and wsad[map[i][j - 1]].d) {
count += replace(New, i, j - 1, ij - 1);
}
if (wsad[map[i][j]].d and j < m - 1 and ij[1] == 0 and wsad[map[i][j + 1]].a) {
count += replace(New, i, j + 1, ij + 1);
}
return count;
}
int Replace(const int New, int i, int j, int* ij) {
int count = 1;
restart:
*ij = New;
WSAD now{
wsad[map[i][j]].w and i > 0 and ij[-m] == 0 and wsad[map[i - 1][j]].s,
wsad[map[i][j]].s and i < n - 1 and ij[m] == 0 and wsad[map[i + 1][j]].w,
wsad[map[i][j]].a and j > 0 and ij[-1] == 0 and wsad[map[i][j - 1]].d,
wsad[map[i][j]].d and j < m - 1 and ij[1] == 0 and wsad[map[i][j + 1]].a
};
if (now.sum() == 1) {
++count;
if (now.w) {
--i;
ij -= m;
}
else if (now.s) {
++i;
ij += m;
}
else if (now.a) {
--j;
--ij;
}
else {
++j;
++ij;
}
goto restart;
}
else {
if (now.w) {
count += Replace(New, i - 1, j, ij - m);
}
if (now.s and ij[m] == 0) {
count += Replace(New, i + 1, j, ij + m);
}
if (now.a and ij[-1] == 0) {
count += Replace(New, i, j - 1, ij - 1);
}
if (now.d and ij[1] == 0) {
count += Replace(New, i, j + 1, ij + 1);
}
}
return count;
}
ZeroJudge Forum