描述-
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表示西墻，2表示北墻，4表示東墻，8表示南墻，將1/2/4/8轉換為2進制為0001/0010/0100/1000，所以判斷有沒有墻就用已知數字與1/2/4/8做&運算。
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
int R,C; //行列數
int rooms[60][60];
int color[60][60]; // 方塊是否染過色的標記
int maxRoomArea = 0, roomNum=0;
int roomArea;
void Dfs(int i,int k){if(color[i][k])return ;++ roomArea;color[i][k] = roomNum;if((rooms[i][k]&1)==0) Dfs(i,k-1); //向西走if((rooms[i][k]&2)==0) Dfs(i-1,k); // 向北走if((rooms[i][k]&4)==0) Dfs(i,k+1); //向西if((rooms[i][k]&8)==0) Dfs(i+1,k); //向南}
int main()
{cin >> R >> C;for(int i=1;i<=R;++i)for(int k=1;k<=C;++k)cin >> rooms[i][k];memset(color, 0 ,sizeof(color));for(int i=1;i<=R;++i)for(int k=1;k<=C;++k){if(!color[i][k]){++ roomNum; roomArea = 0;Dfs(i,k);maxRoomArea = max(roomArea,maxRoomArea);}}cout << roomNum <<endl;cout << maxRoomArea <<endl;
}
)
)
