2.1.1The Castle城堡
时间： 1ms 内存：64M
描述：
我们憨厚的USACO主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡！
喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。
城堡的平面图被划分成M*N(1 <=M,N<=50）个正方形的单位，一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。） 请仔细研究下面这个有注解的城堡平面图：
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # -># | | | | # # ############################## =墙壁 -,| = 没有墙壁
-> =指向一面墙，这面墙推掉的话我们就有一间最大的新房间友情提示，这个城堡的平面图是7×4个单位的。一个“房间”指的是平面图中一个连通的“正方形单位”的集合。比如说这个样例就有5个房间。（大小分别为9、7、3、1、8个单位（排名不分先后））
移去箭头所指的那面墙，可以使2个房间合为一个新房间，且比移去其他墙所形成的房间都大。（原文为：Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. ）
城堡保证至少有2个房间，而且一定有一面墙可以被移走。
输入：
城堡的平面图用一个由数字组成的矩阵表示，一个数字表示一个单位，矩阵有N行M列。输入与样例的图一致。
每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙城堡内部的墙会被规定两次。比如说（1，1）南面的墙，亦会被标记为（2，1）北面的墙。
输出：
输出包含如下4行:
第 1 行: 城堡的房间数目。
第 2 行: 最大的房间的大小
第 3 行: 移除一面墙能得到的最大的房间的大小
第 4 行: 移除哪面墙可以得到面积最大的新房间。
选择最佳的墙来推倒。有多解时选（重心）最靠西的（仍然有多解时选这些里面（重心）最靠南的）。用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（"N"（北）或者"E"（东））。
示例输入：
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
示例输出：
5
9
16
4 1 E
提示：
参考答案（内存最优[788]）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXDIM 50
#define MAXROOM (MAXDIM*MAXDIM)
enum {
Wwest = 1,
Wnorth = 2,
Weast = 4,
Wsouth = 8
};
typedef struct Square Square;
struct Square {
int wall;
int numbered;
int room;
};
int wid, ht;
Square castle[MAXDIM][MAXDIM];
int roomsize[MAXROOM];
void number(int room, int x, int y)
{
int w;
if(castle[x][y].numbered) {
if(castle[x][y].room == room)
return ;
}
castle[x][y].numbered = 1;
castle[x][y].room = room;
roomsize[room]++;
w=castle[x][y].wall;
if(x > 0 && !(w & Wwest))
number(room, x-1, y);
if(x+1 < wid && !(w & Weast))
number(room, x+1, y);
if(y > 0 && !(w & Wnorth))
number(room, x, y-1);
if(y+1 < ht && !(w & Wsouth))
number(room, x, y+1);
}
int main()
{
int x, y, w, nroom, bigroom;
int i, n, m, mx, my;
char mc;
scanf("%d %d", &wid, &ht);
for(y=0; y<ht; y++) {
for(x=0; x<wid; x++) {
scanf("%d", &w);
castle[x][y].wall = w;
}
}
nroom = 0;
for(y=0; y<ht; y++)
for(x=0; x<wid; x++)
if(!castle[x][y].numbered)
number(nroom++, x, y);
bigroom = roomsize[0];
for(i=1; i<nroom; i++)
if(bigroom < roomsize[i])
bigroom = roomsize[i];
m = 0;
for(x=0; x<wid; x++)
for(y=ht-1; y>=0; y--) {
if(y > 0 && castle[x][y].room != castle[x][y-1].room) {
n = roomsize[castle[x][y].room] + roomsize[castle[x][y-1].room];
if(n > m) {
m = n;
mx = x;
my = y;
mc = 'N';
}
}
if(x+1 < wid && castle[x][y].room != castle[x+1][y].room) {
n = roomsize[castle[x][y].room] + roomsize[castle[x+1][y].room];
if(n > m) {
m = n;
mx = x;
my = y;
mc = 'E';
}
}
}
printf("%d\n", nroom);
printf("%d\n", bigroom);
printf("%d\n", m);
printf("%d %d %c\n", my+1, mx+1, mc);
return 0;
}参考答案（时间最优[3]）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXDIM 50
#define MAXROOM (MAXDIM*MAXDIM)
enum {
Wwest = 1,
Wnorth = 2,
Weast = 4,
Wsouth = 8
};
typedef struct Square Square;
struct Square {
int wall;
int numbered;
int room;
};
int wid, ht;
Square castle[MAXDIM][MAXDIM];
int roomsize[MAXROOM];
void number(int room, int x, int y)
{
int w;
if(castle[x][y].numbered) {
if(castle[x][y].room == room)
return ;
}
castle[x][y].numbered = 1;
castle[x][y].room = room;
roomsize[room]++;
w=castle[x][y].wall;
if(x > 0 && !(w & Wwest))
number(room, x-1, y);
if(x+1 < wid && !(w & Weast))
number(room, x+1, y);
if(y > 0 && !(w & Wnorth))
number(room, x, y-1);
if(y+1 < ht && !(w & Wsouth))
number(room, x, y+1);
}
int main()
{
int x, y, w, nroom, bigroom;
int i, n, m, mx, my;
char mc;
scanf("%d %d", &wid, &ht);
for(y=0; y<ht; y++) {
for(x=0; x<wid; x++) {
scanf("%d", &w);
castle[x][y].wall = w;
}
}
nroom = 0;
for(y=0; y<ht; y++)
for(x=0; x<wid; x++)
if(!castle[x][y].numbered)
number(nroom++, x, y);
bigroom = roomsize[0];
for(i=1; i<nroom; i++)
if(bigroom < roomsize[i])
bigroom = roomsize[i];
m = 0;
for(x=0; x<wid; x++)
for(y=ht-1; y>=0; y--) {
if(y > 0 && castle[x][y].room != castle[x][y-1].room) {
n = roomsize[castle[x][y].room] + roomsize[castle[x][y-1].room];
if(n > m) {
m = n;
mx = x;
my = y;
mc = 'N';
}
}
if(x+1 < wid && castle[x][y].room != castle[x+1][y].room) {
n = roomsize[castle[x][y].room] + roomsize[castle[x+1][y].room];
if(n > m) {
m = n;
mx = x;
my = y;
mc = 'E';
}
}
}
printf("%d\n", nroom);
printf("%d\n", bigroom);
printf("%d\n", m);
printf("%d %d %c\n", my+1, mx+1, mc);
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。