배달

*visited를 4차원 배열로 선언 

X좌표 / Y좌표 / 방향 / S와 C를 방문한 상태 

*상태표시는 비트마스크를 사용해서 S까지 총 2^3개를 만들면 된다. 

*C에 도착했을 때 status가 111 이면 배달을 마친 상태이다. (최소값 찾기)

*큐에는 4가지 정보를 모두 저장해서 이전에 방문했던 방향으로 다시 가지 않도록 한다. 

 

#include <iostream> #include <vector> #include <queue> #include <cstring> #define INF 987654321 using namespace std; int n, m, ans = INF; char map[51][51]; typedef pair<int, int> pp; pp start, dest1, dest2; int dx[5] = { 0,0,0,-1,1 }, dy[5] = {0, -1,1,0,0 }; bool visited[51][51][5][1 << 3]; typedef pair<pp, pp> pppp; vector<pp> v; void bfs() { queue<pppp> q; q.push(pppp(pp(1, 0), start)); memset(visited, 0, sizeof(visited)); visited[start.first][start.second][0][1] = true; int cnt = 0, res = INF; while (!q.empty()) { int size = q.size(); while (size--) { pp now = q.front().second; int dir = q.front().first.second; int state = q.front().first.first; q.pop(); if (now == dest1 || now == dest2) { if (state == (1 << 3) - 1) { ans = min(ans, cnt); continue; } } for (int i = 1; i <= 5; i++) { if (i == dir) continue; //연속된 방향으로 또 가면 안된다. int nx = now.first + dx[i]; int ny = now.second + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny][i][state] || map[nx][ny] == '#') continue; if (map[nx][ny] == 'C') { if (dest1 == pp(nx, ny)) { if ((state & (1 << 1)) == 0) { visited[nx][ny][i][state | (1 << 1)] = true; q.push(pppp(pp(state | (1 << 1), i), pp(nx, ny))); } } else if (dest2 == pp(nx, ny)) { if ((state & (1 << 2)) == 0) { visited[nx][ny][i][state | (1 << 2)] = true; q.push(pppp(pp(state | (1 << 2), i), pp(nx, ny))); } } } else { visited[nx][ny][i][state] = true; q.push(pppp(pp(state, i), pp(nx, ny))); } } } cnt++; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; bool flag = false; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) { map[i][j] = s[j]; if (map[i][j] == 'S') { v.insert(v.begin(), pp(i, j)); start = pp(i, j); } else if (map[i][j] == 'C') { v.push_back(pp(i, j)); if (!flag) { flag = true; dest1 = pp(i, j); } else dest2 = pp(i, j); } } } bfs(); //매 시간마다 방향을 바꿔야 하낟. (같은 방향ㅇ으로 두번 연속 이동할 수 없다. ) if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }