描述

1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(圖 1)

# = Wall
| = No wall
- = No wall

圖1是一個城堡的地形圖。請你編寫一個程序，計算城堡一共有多少房間，最大的房間有多大。城堡被分割成m?n(m≤50，n≤50)個方塊，每個方塊可以有0~4面墻。
輸入程序從標準輸入設備讀入數據。第一行是兩個整數，分別是南北向、東西向的方塊數。在接下來的輸入行里，每個方塊用一個數字(0≤p≤50)描述。用一個數字表示方塊周圍的墻，1表示西墻，2表示北墻，4表示東墻，8表示南墻。每個方塊用代表其周圍墻的數字之和表示。城堡的內墻被計算兩次，方塊(1,1)的南墻同時也是方塊(2,1)的北墻。輸入的數據保證城堡至少有兩個房間。輸出城堡的房間數、城堡中最大房間所包括的方塊數。結果顯示在標準輸出設備上。
樣例輸入

4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13

樣例輸出

5 9 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 int n, m;//行數，列數 7 int room[51][51];//保存房間信息 8 int color[51][51];//標記數組，用來檢查一個房間是否已經走過 9 int roomNum = 0, maxArea = 0;//總的房間數和最大房間面積 10 int area = 0;//當前正在走的房間的面積 11 void dfs(int i,int j)//對當前位置做dfs，會得到該房間所在的聯通分量 12 { 13 //cout << "dfs(" << i << "," << j << ")" << endl; 14 if (color[i][j])//為舊點 15 { 16 //cout << "(" << i << "," << j << ")是舊點" << endl; 17 return; 18 } 19 //cout << "(" << i << "," << j << ")不是舊點" << endl; 20 area++; 21 //標記為舊點 22 color[i][j] = roomNum; 23 //按西北東南的順序做dfs，本題不用考慮邊界問題，因為輸入保證了四周都有墻，dfs一定會在到達邊界的時候停下來 24 if (!(room[i][j] & 1))//西邊沒有墻往西走 25 { 26 //cout << "(" << i << "," << j << ")西邊沒有墻往西走" << endl; 27 dfs(i, j - 1); 28 } 29 30 if (!(room[i][j] & 2))//北邊沒有墻往北走 31 { 32 //cout << "(" << i << "," << j << ")北邊沒有墻往北走" << endl; 33 dfs(i - 1, j); 34 } 35 36 if (!(room[i][j] & 4))//東邊沒有墻往東走 37 { 38 //cout << "(" << i << "," << j << ")東邊沒有墻往東走" << endl; 39 dfs(i, j + 1); 40 } 41 42 if (!(room[i][j] & 8))//南邊沒有墻往南走 43 { 44 //cout << "(" << i << "," << j << ")南邊沒有墻往南走" << endl; 45 dfs(i + 1, j); 46 } 47 48 } 49 int main() 50 { 51 cin >> n >> m; 52 memset(room,0,sizeof(room)); 53 memset(color, 0, sizeof(color)); 54 for (int i = 1; i <= n; ++i) 55 for (int j = 1; j <= m; ++j) 56 cin >> room[i][j]; 57 58 for (int i = 1; i <= n; ++i) 59 for (int j = 1; j <= m; ++j) 60 { 61 if (!color[i][j])//這個房間沒有被走過 62 { 63 roomNum++; 64 area = 0; 65 dfs(i,j); 66 maxArea = max(maxArea,area); 67 } 68 } 69 cout << roomNum << endl; 70 cout << maxArea << endl; 71 return 0; 72 }

?

轉載于:https://www.cnblogs.com/knmxx/p/9546872.html

總結

以上是生活随笔為你收集整理的百练2815:城堡问题（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。