Problem 2.1.3 The Castle

출처: https://train.usaco.org/usacogate

---

문제 설명

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.

 

입력

Line 1: Two space-separated integers: M and N
Line 2..: M x N integers, several per line.

출력

Line 1: The number of rooms the castle has.
Line 2: The size of the largest room
Line 3: The size of the largest room creatable by removing one wall
Line 4: The single wall to remove to make the largest room possible

입력 예

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

---

문제 풀이

IOI'94 - Day 1 의 문제이다. N x M maze에서 연결된 방들을 채워가는 Flood fill 알고리즘을 적용하면, 전체 연결된 방을 알 수 있다. 한방에서 연결된 방을 찾아가는 방법은 DFS가 적용된다.  N x M maze를 다루는 연습이 필요한 문제이다. 벽을 제거하면서 값을 비교할때는 항상 계산이 끝난 다음 원래 값으로 변경시키는 과정을 적용해야 한다.

프로그램 내용

void fill_cells(int y, int x, int& direction)
{
    if(visited[y][x]) return;
    visited[y][x] = 1;
    before[y][x] = roomNumber;
    direction++;

    if(!(cells[y][x] & 1)) fill_cells(y,x-1, direction); /// Connected Direction: W
    if(!(cells[y][x] & 2)) fill_cells(y-1,x, direction); /// Connected Direction: N
    if(!(cells[y][x] & 4)) fill_cells(y,x+1, direction); /// Connected Direction: E
    if(!(cells[y][x] & 8)) fill_cells(y+1,x, direction); /// Connected Direction: S
};
...

한 방에 도착하면 연결된 벽을 확인하고, 벽으로 막혀 있지 않으면 그 방까지 연결한다.

 /// visit every rooms
    for(int y=1; y <N+1; ++y)
    {
        for(int x=1; x<M+1;++x)
        {
            if(!visited[y][x])
            {
                roomNumber++;
                int tn=0;
                fill_cells(y,x,tn);
                room[roomNumber] = tn;
                if( tn > maxn ) maxn = tn;
            }
        }
    }

    /// remove wall check
    for(int j=1;j<=M;j+=1)
    {
        for(int i=N;i>=1;i-=1)
        {
            if(cells[i][j]&2)if(before[i-1][j] && before[i-1][j]!=before[i][j])
            {
                if( room[before[i-1][j]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i-1][j]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'N';
                }
            }

            if(cells[i][j]&4)if(before[i][j+1] && before[i][j+1]!=before[i][j])
            {
                if( room[before[i][j+1]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i][j+1]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'E';
                }
            }
        }
    }

전체 방에 대해서 벽을 제거해서 결과값이 최대가 될때마다 제거하는 벽을 기록하는 방법을 적용한다.

 

Chapter 2. Bigger Challenges ( link )