1175 - 배달

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

2차원 평면에서 S부터 2개의 C블럭을 모두 도달하는 최단 거리 BFS인데 조건이 있다.

같은 방향으로 2번 이상 이동할 수가 없다.

원래 BFS를 할때 visit[N][M] 처럼 했다면, "어디쪽에서 왔는가"도 추가해야한다.

그리고 2개의 C블럭을 모두 도달해야 한다. 이것을 C0, C1 으로 부른다면 어떤 지점까지 움직였을 때, 문제를 얼만큼 해결했는 가를 4가지 상태로 나타낼 수 있다.

1. C0, C1 을 모두 못 찾았다.
2. C0 을 찾았다
3. C1 을 찾았다.
4. C0, C1 을 모두 찾았다.

(C0를 찾았다, C1를 찾았다) 로 표현한다면 00, 10, 01, 11 로 나타낼 수 있고, 이를 2진수로 본다면 10진수 0, 2, 1, 3 이다.

4번의 상태가 나올때까지, 같은 방향으로 진행하지 않으면서, 이전에 왔던 위치에 이전과 똑같은 움직임으로 다시 방문하지 않고 (visit[y][x][previousDirect]), 그 때의 '얼만큼 찾았는 가'의 상태마저 같지 않은 경우만 탐색하면 된다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

const int DX[]={-1, 0, 1, 0};
const int DY[]={ 0,-1, 0, 1};

struct gift {
    int y, x, t;
    char prevDirect;
    char cBit;
};

int main(){
    int i, j, d, h, w;
    scanf("%d %d ", &h, &w);
    char s[51][51]={};
    for(i=0; i<h; ++i) scanf("%s ", s[i]);
    
    int cost[51][51][4][4];
    int startX=-1, startY=-1, totalC = 0;
    int cx[2], cy[2];
    for(i=0; i<h; ++i){
        for(j=0; j<w; ++j){
            if(s[i][j]=='S'){
                startX = j; startY = i;
            }
            if(s[i][j]=='C'){
                cx[totalC] = j;
                cy[totalC++] = i;
            }
        }
    }
    
    for(i=0; i<51; ++i){
        for(j=0; j<51; ++j){
            for(d=0; d<16; ++d)
                cost[i][j][d/4][d%4] = INF;
        }
    }
    
    queue<gift> q;
    q.push({startY, startX, 0, -1, 0});
    int minCost = INF;
    while(!q.empty()){
        gift cur = q.front();
        q.pop();
        if(cur.cBit == 3){
            minCost = min(minCost, cur.t);
            continue;
        }
        for(i=0; i<4; ++i){
            if(i == cur.prevDirect) continue;
            int dy = cur.y+DY[i], dx = cur.x+DX[i];
            if(dy < 0 || dx < 0 || dy >= h || dx >= w || s[dy][dx] == '#' || cur.t+1 >= cost[dy][dx][i][cur.cBit]) continue;
            if((cur.cBit&1)==1 && cx[0]==dx && cy[0]==dy ) continue;
            if((cur.cBit&2)==2 && cx[1]==dx && cy[1]==dy ) continue;
            q.push({dy, dx, cur.t+1, i, cur.cBit | ((cx[1]==dx&&cy[1]==dy)<<1) | (cx[0]==dx&&cy[0]==dy)});
            cost[dy][dx][i][cur.cBit] = cur.t+1;
        }
    }
    printf("%d", minCost<INF?minCost:-1);
    
    return 0;
}