# 2.1.1The Castle城堡

2.1.1The Castle城堡

``` 1   2   3   4   5   6   7
#############################
1 #   |   #   |   #   |   |   #
#####---#####---#---#####---#
2 #   #   |   #   #   #   #   #
#---#####---#####---#####---#
3 #   |   |   #   #   #   #   #
#---#########---#####---#---#
4 # ->#   |   |   |   |   #   #
#############################
```

# =墙壁 -,| = 没有墙壁
-> =指向一面墙，这面墙推掉的话我们就有一间最大的新房间

1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙

``````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
``````

``````#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;
}``````

``````#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;
}``````