[BOJ-2931]가스관

https://www.acmicpc.net/problem/2931

추가데이터는 아래에서 확인가능하다.

http://hsin.hr/2009/

[접근방법]

시뮬레이션

BFS를 사용할 수도 있음.

DFS를 사용할 수도 있음.

비트연산자로 흐르는 위치를 모두 표시함.

1 << 0 ; 위쪽

1 << 1 ; 왼쪽

1 << 2 ; 아래쪽

1 << 3 ; 오른쪽

그리고 M과 Z 인 경우는 체크하지 않게 하였다.

1) 설치할 수 있는 가스관을 확인. 

어느쪽에서 흐르던지 설치해야하는 가스관은 비트마스크로 표시하였다. 

만나게 되면, 일치하는 가스관이 있는지 확인하고 출력을 한 후 마친다.

2) 1)의 경우에 확인되지 않는 경우는 M과 Z 사이 거리가 1 인 경우이다. 

M.Z 

M

.

Z

.M

Z.

인 경우 이므로 확인을 해서 출력한다. 만약 1)의 경우에서 값이 나온 경우, 이미 종료하였으므로 2)를 확인하지 않는다.

[C++ source code]

#include<cstdio>
#define din1(a) scanf("%d",&a)
const int M = 33;
char imap[M][M];
int vis[M][M];
 
const int dr[] = { -1,0,1,0 }; // U L D R
const int dc[] = { 0,-1,0,1 };
 
const int flow[] = { 1 << 0, 1 << 1, 1 << 2, 1 << 3 }; // ULDR
 
struct pipe {
    char block;
    int flow_d;
    pipe() :block(0), flow_d(0) {}
    void set_pipe(char ib, int iflow) {
        block = ib;
        flow_d = iflow;
    }
};
 
const int N = 9;
pipe bn[9];
const char block_c[] = { '|', '-', '+', '1', '2', '3', '4', 'M', 'Z' };
const char block_f[] = {
    flow[0] | flow[2],
    flow[1] | flow[3],
    flow[0] | flow[1] | flow[2] | flow[3],
    flow[2] | flow[3],
    flow[0] | flow[3],
    flow[0] | flow[1],
    flow[1] | flow[2],
    flow[0] | flow[1] | flow[2] | flow[3],
    flow[0] | flow[1] | flow[2] | flow[3],
};
 
void init() {
    for (int i = 0; i < 9; i++) {
        bn[i].set_pipe(block_c[i], block_f[i]);
    }
}
 
int main() {
    int row, col;
    din1(row);
    din1(col);
    init();
    for (int r = 0; r < row; r++) {
        scanf("%s", imap[r]);
    } // input 
 
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (imap[r][c] == '.') continue;
            if (imap[r][c] == 'M' || imap[r][c] == 'Z') continue;
            pipe here;
            here.set_pipe(imap[r][c], 0);
 
            for (int i = 0; i < N; i++) {
                if (here.block == bn[i].block) {
                    here.flow_d = bn[i].flow_d;
                    break;
                }
            }
 
            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];
 
                if (tr < 0 || tc < 0 || row <= tr || col <= tc) continue; // range over                
                if ((here.flow_d & flow[i]) != flow[i]) continue; // impossible i-th dir flow
 
                int there_flow = flow[(i + 2) % 4];
                vis[tr][tc] += there_flow;                
            }
        }
    } // flow 
 
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (imap[r][c] != '.') continue;
            if (vis[r][c] == 0) continue;
 
            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];
                if (tr < 0 || tc < 0 || row <= tr || col <= tc) continue; // range over                
                if (imap[tr][tc] == 'M' || imap[tr][tc] == 'Z') {
                    int there_flow = flow[i];
                    vis[r][c] = vis[r][c] | there_flow;
                }
            }
 
            for (int i = 0; i < 7; i++) {
                if (vis[r][c] == bn[i].flow_d) {
                    printf("%d %d %c\n", r + 1, c + 1, bn[i].block);
                    return 0;
                }
            }
        }
    }
 
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (imap[r][c] != '.') continue;
            //if (vis[r][c] == 0) continue;
 
            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];
                if (tr < 0 || tc < 0 || row <= tr || col <= tc) continue; // range over                
                if (imap[tr][tc] == 'M' || imap[tr][tc] == 'Z') {
                    int there_flow = flow[i];
                    vis[r][c] = vis[r][c] | there_flow;
                }
            }
 
            for (int i = 0; i < 7; i++) {
                if (vis[r][c] == bn[i].flow_d) {
                    printf("%d %d %c\n", r + 1, c + 1, bn[i].block);
                    return 0;
                }
            }
        }
    }
 
    return 0;
}
/*
@test case
2 4
M14Z
232.

2 4
M.-Z
23..

2 4
M.-Z
....

6 6
1--M.Z
24..1.
.|.13.
.|.24.
.|1-3.
.23...
*/