#38469: 用遞迴
alec5106@gmail.com
(Alec Chen)
學校
:
不指定學校
編號 : 237442
來源 : [163.27.125.135]
最後登入時間 ：
2023-11-27 14:46:35
#39459: Re: 用遞迴
試著用遞迴去跑. 可以完整通過. 速度 41ms
我就是用遞迴寫，速度10ms。95%
然後在最後一題堆疊爆了。125250層的遞迴......只有1MB的堆疊空間顯然不夠。
#include<iostream>#include<memory>#include<vector>#include<algorithm>int n = 0, m = 0; //宣告為全域變數，這樣就可以在直接在函式中使用了(偷懶作法)char map[500][501] = {};struct {bool w;bool s;bool a;bool 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();std::vector<int> count(1); //這個陣列用於統計各連通塊的大小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; }count.push_back(replace(count.size(), i, j, array + (i * m + j)));}}//這段程式碼可以輸出下水道中水管連接的狀況，你可以試著執行看看//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 << *std::max_element(count.begin()+1, count.end());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;}
#39466: Re: 用遞迴
把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, 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