[bfs] dam

 

프로그램 명: dam(open)

제한시간: 1 초

어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.

당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다.

입력

• 첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고
• 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.)
• 그리고 그 다음 줄에는 호수의 좌표 x, y가 주어지고,
• 다음 줄에는 댐이 지어지는 시간인 K가 주어진다.

출력

지어야 하는 댐의 숫자를 출력한다. 만약, 마을이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "OH, MY GOD"을 출력한다. (좋은 의미로든, 나쁜 의미로든....)

입출력 예

입력

5
0 1 0 0 1
0 0 0 0 0
1 1 1 0 1
0 0 0 0 0
1 0 1 0 1
1 1
5

출력

3

입력

5
0 0 1 0 0
0 0 0 0 0
1 1 1 0 0
0 0 1 1 0
0 0 0 0 0
5 2
3

출력

2

입출력 설명

첫 번째 입력에서 (1,1) 위치에서 물이 터졌다면, 물은 시간마다 다음과 같이 진행된다.
(B는 건물의 위치)

0 B 4 5 B
1 2 3 4 5
B B B 5 B
9 8 7 6 7
B 9 B 7 B

그러므로 5 시간인 세군데를 막아 물이 진행하지 못하게 하는 것이 최선이다.
그러므로 출력이 3

출처:Ceil

 

 

#include <stdio.h>
 
#define MAX 105
 
int Map[MAX][MAX];
int QueMap[MAX*MAX][2];
int QueDepth[MAX*MAX];
 
int T, K;
int StartX, StartY;
 
int Dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
int Rear=1, Head=1;
 
void enQue(int x, int y)
{
    QueMap[Rear][0] = x;
    QueMap[Rear][1] = y;
    QueDepth[Rear] = QueDepth[Head-1] + 1;
    Rear++;
}
 
void deQue(int* x, int* y)
{
    *x = QueMap[Head][0];
    *y = QueMap[Head][1];
    Head++;
}
 
void input()
{
    int x, y;
    scanf("%d", &T);
    for(y = 1; y <= T; y++)
    {
        for(x = 1; x <= T; x++)
        {
            scanf("%d", &Map[y][x]);
            Map[y][x] += 1;
        }
    }
 
    scanf("%d %d", &StartX, &StartY);
    scanf("%d", &K);
}
 
void bfs(int x, int y)
{
    int i;
    int depth;
 
    enQue(x, y);
    Map[y][x] = QueDepth[Rear-1] + 3;
    while(Rear >= Head)
    {
        deQue(&x, &y);
        
        for(i = 0; i < 4; i++)
        {
            if(Map[ y + Dir[i][1] ][ x + Dir[i][0] ] == 1)
            {
                enQue( x + Dir[i][0], y + Dir[i][1] );
                Map[y + Dir[i][1]][x + Dir[i][0]] = QueDepth[Rear-1] + 3;
            }
        }
    }    
}
 
void output()
{
    int i, j, count =0;
 
    for(i = 1; i <= T; i++)
    {
        for(j = 1; j <= T; j++)
        {
            if(Map[i][j] - 4 == K)
                count ++;
        }
    }
 
    if(count != 0)
        printf("%d\n", count);
    else
        printf("OH, MY GOD\n");
}
 
int main(void)
{
    input();
    bfs(startX, startY);
    output();
    return 0;
}