題目要求

總時間限制:1000ms
內存限制:65536kB

題目描述

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

題目鏈接

http://bailian.openjudge.cn/practice/2815/

分析

第一步：先看圖，這就要看想象力了，要把#都想象成墻，然后大致能想象出來出來這是一個城堡的平面圖。

第二步：看輸入，有四個很奇怪的數字，1，2，4，8。為什么要用這四個數表示東西南北墻？如果把它們轉換成二進制的數，對應的就是0001，0010，0100，1000，這樣就知道題目的意圖了，用位運算進行判斷墻面。

第三步：選擇合適的數據結構進行匹配。把方塊看作是節點，相鄰兩個方塊之間如果沒有墻，則在方塊之間連一條邊，這樣城堡就能轉換成一個圖。

第四步：問題抽象。
求房間個數，實際上就是在求圖中有多少個極大連通子圖（一個連通子圖，往里面加任何一個圖里的其它點，就會變得不連通，那么這個連通子圖就是極大連通子圖）。
每一個房間，深度優先搜索，從而給這個房間能夠到達的所有位置染色。最后統計一共有用了幾種顏色，以及每種顏色的數量。

代碼塊

1.需要的變量以及頭文件：

#include <iostream> #include <stack> #include <cstring> using namespace std; int R,C; //行列數 int rooms[60][60]; //存放整個城堡的方塊 int color[60][60]; //方塊是否染色過的標記 int maxRoomArea=0; //用來表示最大的房間面積 int roomNum=0; //表示當前已經找到的房間數目 int roomArea; //表示正在探索的房間的面積

2.判斷墻面是否存在：

if((rooms[i][k]&1)==0) //西if((rooms[i][k]&2)==0) //北if((rooms[i][k]&4)==0) //東if((rooms[i][k]&8)==0) //南

3.剩下的就是讀入數據以及進行操作了。

完整代碼

#include <iostream> #include <stack> #include <cstring> using namespace std; int R,C; //行列數 int rooms[60][60]; //存放整個城堡的方塊 int color[60][60]; //方塊是否染色過的標記 int maxRoomArea=0; //用來表示最大的房間面積 int 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 城堡问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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