[1175] 배달

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

1175번: 배달

<문제>

"[16933] 벽 부수고 이동하기 3"과 "[1194] 달이 차오른다, 가자."를 묘하게 섞었다.

하나의 상태를 잘 정의해주어야 하는데, (y, x)는 자명하니, 상태를 구성하는 다른 요소를 살펴보자.

 

벽 부수고 이동하기 3 처럼 이전방향의 이동에 대한 정보를 저장해야 한다.

벽 부수고 이동하기는 현재의 turn이 짝수이냐와 홀수이냐를 이용해 상태가 달라졌다면,

이 문제는 이전에 어느 방향에서 왔는지로 상태가 달라진다.

queue에 push할때, 4방향 for문을 돌리는 변수를 그대로 넣어주는 방식으로 구현하면 된다.

또한, 배달을 두 번 완료해야 하므로, 비트마스킹을 이용해서 상태를 표현해줄 수 있다.

배달에 대한건 결국 [0, (1<<2) ) 안의 값으로 표현되므로 최종적으로 vst[y][x][dir][bt]로 방문처리하면 된다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};

char a[55][55];

bool vst[55][55][4][4];

vector<pi> v;

typedef struct {

    int y, x, d, bt, turn;

} state;

int f(int sy, int sx) {

    queue<state> q;

    int i;

    for (i = 0; i < 4; i++) q.push({sy, sx, i, 0, 0});

    while (!q.empty()) {

        state cur = q.front();

        q.pop();

        if (a[cur.y][cur.x] == '1') {

            if ((cur.bt & 1) == 0) cur.bt |= 1;

        }

        if (a[cur.y][cur.x] == '2') {

            if ((cur.bt & 2) == 0) cur.bt |= 2;

        }

        if (cur.bt == 3) return cur.turn;

        for (i = 0; i < 4; i++) {

            if (i == cur.d) continue;

            int y = cur.y + dy[i];

            int x = cur.x + dx[i];

            if (y < 0 || x < 0 || y >= n || x >= m) continue;

            if (a[y][x] == '#') continue;

            if (vst[y][x][i][cur.bt] == false) {

                vst[y][x][i][cur.bt] = true;

                q.push({y, x, i, cur.bt, cur.turn + 1});

            }

        }

    }

    return -1;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> m;

    int i, j, sy, sx;

    for (i = 0; i < n; i++)

        for (j = 0; j < m; j++) {

            cin >> a[i][j];

            if (a[i][j] == 'S')

                sy = i, sx = j;

            else if (a[i][j] == 'C') {

                char x = '1' + v.size();

                v.push_back({i, j});

                a[i][j] = x;

            }

        }

    cout << f(sy, sx);

    return 0;

}