生活随笔
收集整理的這篇文章主要介紹了
2815:城堡问题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
2815:城堡問題
總時間限制:?
1000ms?內存限制:?
65536kB 描述
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面墻。
輸入
程序從標準輸入設備讀入數(shù)據(jù)。第一行是兩個整數(shù)，分別是南北向、東西向的方塊數(shù)。在接下來的輸入行里，每個方塊用一個數(shù)字(0≤p≤50)描述。用一個數(shù)字表示方塊周圍的墻，1表示西墻，2表示北墻，4表示東墻，8表示南墻。每個方塊用代表其周圍墻的數(shù)字之和表示。城堡的內墻被計算兩次，方塊(1,1)的南墻同時也是方塊(2,1)的北墻。輸入的數(shù)據(jù)保證城堡至少有兩個房間。輸出
城堡的房間數(shù)、城堡中最大房間所包括的方塊數(shù)。結果顯示在標準輸出設備上。
樣例輸入
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
來源
把方塊看作是節(jié)點，若沒墻表示連通，進而將它轉換為一個圖，求房間個數(shù)，就是求有幾個最大連通子圖。 求最大的房間就是求最大的連通子圖的節(jié)點數(shù)。使用深搜方法，將能夠到達的房間進行染色，最后統(tǒng)計一共用了多少顏色。1表示西墻，2表示北墻，4表示東墻，8表示南墻，將1/2/4/8轉換為2進制為0001/0010/0100/1000，所以判斷有沒有墻就用已知數(shù)字與1/2/4/8做&運算。
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
int R,C; //行列數(shù)
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;
}
總結
以上是生活随笔為你收集整理的2815:城堡问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。
