1953. [모의 SW 역량테스트] 탈주범 검거

요건 약 1시간 컷.

BFS 문제이다. 모든 문제가 그렇듯이 BFS + 약간 응용 이다.

주의 점.

1. 현재 파이프에서 다음 파이프가 이어져서 갈 수 있는지 판단.

2. 같은 시간마다 퍼져야 하는 모든 칸을 동시에 체크.

1번 구현은 했는데 먼가 간단히 할 수 있을 것 같지만..귀찮!!

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
 
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int map[55][55], visit[55][55];
int N, M, R, C, L, NUM, Q_Front, Q_Back;
 
point Q[50 * 50];
 
int CanIgo(int now, int next, int Derection)
{
    //0 상, 1 하, 2 좌, 3 우.
    switch (now)
    {
    case 1:
        if(Derection == 0 && (next == 1 || next == 2 || next == 5 || next == 6))
            return 1;
        else if (Derection == 1 && (next == 1 || next == 2 || next == 4 || next == 7))
            return 1;
        else if (Derection == 2 && (next == 1 || next == 3 || next == 4 || next == 5))
            return 1;
        else if (Derection == 3 && (next == 1 || next == 3 || next == 6 || next == 7))
            return 1;
    case 2:
        if (Derection == 0 && (next == 1 || next == 2 || next == 5 || next == 6))
            return 1;
        else if(Derection == 1 && (next == 1 || next == 2 || next == 4 || next == 7))
            return 1;
        break;
    case 3:
        if (Derection == 2 && (next == 1 || next == 3 || next == 4 || next == 5))
            return 1;
        else if (Derection == 3 && (next == 1 || next == 3 || next == 6 || next == 7))
            return 1;
        break;
    case 4:
        if (Derection == 0 && (next == 1 || next == 2 || next == 5 || next == 6))
            return 1;
        else if (Derection == 3 && (next == 1 || next == 3 || next == 6 || next == 7))
            return 1;
        break;
    case 5:
        if (Derection == 3 && (next == 1 || next == 3 || next == 6 || next == 7))
            return 1;
        else if (Derection == 1 && (next == 1 || next == 2 || next == 4 || next == 7))
            return 1;
        break;
    case 6:
        if (Derection == 2 && (next == 1 || next == 3 || next == 4 || next == 5))
            return 1;
        else if (Derection == 1 && (next == 1 || next == 2 || next == 4 || next == 7))
            return 1;
        break;
    case 7:
        if (Derection == 0 && (next == 1 || next == 2 || next == 5 || next == 6))
            return 1;
        else if (Derection == 2 && (next == 1 || next == 3 || next == 4 || next == 5))
            return 1;
        break;
    }
    return 0;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1 ; T <= Test_Case; T++)
    {
        Q_Front = Q_Back = -1;
        N = M = R = C = L = NUM = 0;
        memset(map, -1, sizeof(map));
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
 
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                scanf("%d", &map[i][j]);
 
        R++; C++;
        int cnt = 1, temp=0;
        visit[R][C] = 1;
        Q[++Q_Back].y = R;
        Q[Q_Back].x = C;
        
        for(int l = 0 ; l < L - 1 ; l++)
        {
            for (int a = 0; a < cnt; a++)
            {
                int y = Q[++Q_Front].y;
                int x = Q[Q_Front].x;
 
                for (int i = 0; i < 4; i++)
                {
                    int yy = y + dy[i];
                    int xx = x + dx[i];
 
                    if (map[yy][xx] == -1 || visit[yy][xx] == 1 || map[yy][xx] == 0)
                        continue;
 
                    if (CanIgo(map[y][x], map[yy][xx], i) == 1)
                    {
                        Q[++Q_Back].y = yy;
                        Q[Q_Back].x = xx;
                        visit[yy][xx] = 1;
                        temp++;
                     }
                }
            }
            cnt = temp; temp = 0;        
        }
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                if (visit[i][j] == 1)
                    NUM++;
            }
        }
 
 
        printf("#%d %d\n",T, NUM);
    }
 
    return 0;
}