★The Castle 城堡
以一個(gè)幾乎超乎想像的運(yùn)氣,農(nóng)民約翰在他的生日收到了一張愛(ài)爾蘭博彩的獎(jiǎng)券.這一張獎(jiǎng)券成為
了唯一中獎(jiǎng)的獎(jiǎng)券.農(nóng)民約翰嬴得愛(ài)爾蘭的鄉(xiāng)下地方的一個(gè)傳說(shuō)中的城堡.
吹牛在他們威斯康辛州不算什么,農(nóng)民約翰想告訴他的牛所有有關(guān)城堡的事.他想知道城堡有多少
房間,而且最大的房間有多大.事實(shí)上,他想去掉一面墻來(lái)制造一個(gè)更大的房間.
你的任務(wù)是幫助農(nóng)民約翰去了解正確房間數(shù)目和大小.
城堡的平面圖被分為 M(wide)*N(1 <=M,N<=50)個(gè)小正方形.
每個(gè)這樣的小正方形有 0 到 4 面墻.
城堡在它的外部邊緣總是有墻壁的,好遮擋風(fēng)雨.
考慮這注解了一個(gè)城堡的平面圖:
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # -># | | | | # #
#############################
# =墻壁 -, | = 沒(méi)有墻壁
-> =移除這面墻能使得到的新房間最大
例子的城堡的大小是 7 x 4.
一個(gè) "房間"是平面圖上有連接的"小正方形"的集合.
這個(gè)平面圖包含五個(gè)房間.(它們的大小是 9,7,3,1, 和 8 排列沒(méi)有特別的順序).
移除被箭作記號(hào)的墻壁來(lái)合并兩個(gè)房間來(lái)制造最大的可能房間(移除一面墻所能產(chǎn)生的).
城堡總是至少有二個(gè)房間并且總是有一面墻壁以可能被移除.
PROGRAM NAME: castle
INPUT FORMAT
地圖以一個(gè)表格來(lái)儲(chǔ)存,每個(gè)數(shù)字描述一個(gè)小正方形,N 行每行 M 個(gè)數(shù)來(lái)描述這個(gè)平面圖.
輸入順序符合那個(gè)在上面例子的編號(hào)方式.
每個(gè)描述小正方形的數(shù)字說(shuō)明小正方形的四面的墻的分布情況,它是下面 4 個(gè)數(shù)的和:
1: 在西面有墻
2: 在北面有墻
22
4: 在東面有墻
8: 在南面有墻
內(nèi)部的墻壁是會(huì)被定義兩次；小正方形(1,1)南面的墻也被指出是小正方形(2,1)北面的墻.
第 1 行: 二個(gè)被空格分開(kāi)的整數(shù): M 和 N
第 2 到: N+1 行: M x N 個(gè)整數(shù),每行 M 個(gè).
SAMPLE INPUT (file castle.in)
7 4
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
OUTPUT FORMAT
輸出包含一些行:
第 1 行: 城堡的房間數(shù)目.
第 2 行: 最大的房間的大小
第 3 行: 移除一面墻能得到的最大的房間的大小
第 4 行: 移除哪面墻
選擇最佳的墻來(lái)移除,(選擇最靠西的,如果仍然不能確定,再選擇最靠南的.編者注:墻的位置應(yīng)該
由它的中點(diǎn)來(lái)定義)
(【原文】Choose the optimal wall to remove from the set of optimal walls by choosing the
wall farther to the west (and then, if still tied, farthest to the south).)

墻壁由它在相鄰的小正方形的西部或南方來(lái)命名

這題剛看到我就懵逼了，這什么鬼。然后就一直放在那，把2.1其他題目都做完了我又來(lái)搞他,看了題解（一定要耐心看代碼==）慢慢看發(fā)現(xiàn)思路不難（當(dāng)然自己寫(xiě)出來(lái)還是很難），用wall[i][j][k]再用右移運(yùn)算來(lái)判斷是否有墻。知道了思路后我就開(kāi)寫(xiě)了然后。。。。。。。。。媽的。。。。。。一開(kāi)始n,m跟我們平時(shí)的順序不一樣，一個(gè)坑然后）（選擇最佳的墻來(lái)移除,(選擇最靠西的,如果仍然不能確定,再選擇最靠南的.編者注:墻的位置應(yīng)該
由它的中點(diǎn)來(lái)定義)）被這句話(huà)搞成傻逼。

/*
ID:jinbo wu
LANG:C++
TASK: castle
*/
#include<bits/stdc++.h>
using namespace std;
int vis[55][55];
int room[55][55];
int wall[55][55][4];
int roomn;
int size[55*55];
void dfs(int x,int y)
{vis[x][y]=1;if(room[x][y]==roomn)return;room[x][y]=roomn;size[roomn]++;if(!wall[x][y][0]) dfs(x,y-1);if(!wall[x][y][1]) dfs(x-1,y);if(!wall[x][y][2]) dfs(x,y+1);if(!wall[x][y][3]) dfs(x+1,y);
}
int main()
{int n,m,ax,ay;int tmp;int rmax1=0;char c;freopen("castle.in","r",stdin);freopen("castle.out","w",stdout);scanf("%d %d",&m,&n);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>tmp;for(int k=0;k<4;k++)wall[i][j][k]=(tmp>>k)&1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(!vis[i][j]){roomn++;dfs(i,j);rmax1=max(rmax1,size[roomn]);}}cout<<roomn<<endl;cout<<rmax1<<endl;rmax1=0;for(int j=1;j<=m;j++)for(int i=n;i>=1;i--){int room1=room[i][j];int room2=room[i][j+1];int room3=room[i-1][j];if(i>1&&wall[i][j][1]&&room1!=room3&&size[room1]+size[room3]>rmax1){ax=i,ay=j;c='N';rmax1=size[room1]+size[room3];}if(j<m&&wall[i][j][2]&&room1!=room2&&size[room1]+size[room2]>rmax1){ax=i,ay=j;c='E';rmax1=size[room1]+size[room2];}}cout<<rmax1<<endl;cout<<ax<<" "<<ay<<" "<<c<<endl;
}

總結(jié)

以上是生活随笔為你收集整理的usaco The Castle的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。