#include #include #include #include #include using namespace std; int N, M; char Map[11][11]; bool Visited[11][11][11][11]; int DX[4] = {1,0,-1,0}; int DY[4] = { 0,1,0,-1 }; struct Coord { Coord(int _Y, int _X) : Y(_Y), X(_X) {} Coord() {} const bool operator == (const Coord& Other) { return (Y == Other.Y) && (X == Other.X); } const bool operator != (const Coord& Other) { return (Y != Other.Y) || (X != Other.X); } int Y, X; }; Coord HolePos; struct Data { Data() {} Data(const Coord& _RPos, const Coord& _BPos, int _TryNum): RPos(_RPos), BPos(_BPos), TryNum(_TryNum) {} Coord RPos, BPos; int TryNum; }; struct Cmp { const bool operator()(const Data& A, const Data& B) { return A.TryNum > B.TryNum; } }; void Game(Coord RPos, Coord BPos) { // 우선순위큐에 TryNum 기준으로 정렬 priority_queue, Cmp> PQ; PQ.push({ RPos, BPos, 0 }); Visited[RPos.Y][RPos.X][BPos.Y][BPos.X] = true; bool IsFailReserved = false; while (!PQ.empty()) { Data CurData = PQ.top(); Coord CurRPos = CurData.RPos; Coord CurBPos = CurData.BPos; int CurTryNum = CurData.TryNum; PQ.pop(); // 빨간구슬 파란구슬 둘다 벽에의해 막혔을때 카운트 + 1 해야함. for (int i = 0; i < 4; i++) { bool CanMove = false; Coord NextRPos = CurRPos; Coord NextBPos = CurBPos; int NextTryNum = CurTryNum + 1; bool IsHoleOverlapped = false; while (true) { Coord OriginRPos = NextRPos; Coord OriginBPos = NextBPos; NextRPos = { NextRPos.Y + DY[i], NextRPos.X + DX[i] }; NextBPos = { NextBPos.Y + DY[i], NextBPos.X + DX[i] }; // 움직일수 없는조건 bool CanNextR = (Map[NextRPos.Y][NextRPos.X] == '#') || OriginRPos == HolePos; bool CanNextB = (Map[NextBPos.Y][NextBPos.X] == '#') || OriginBPos == HolePos; CanMove = (CanNextR && CanNextB); // true면 이동 끝난것 // 원래의 위치로 돌아와버리는게 문제다. NextRPos = (CanNextR) ? OriginRPos : NextRPos; NextBPos = (CanNextB) ? OriginBPos : NextBPos; // 둘이 예상 위치가 같다면 겹치지않도록해야함, 하지만 그게 구멍이라면? if (NextRPos == NextBPos) { // 큐랑 상관없이 둘이 같긴하다면 둘이 합체를해버린다 그냥 if (NextRPos == HolePos) { IsHoleOverlapped = true; } // 누가 여기로 와서 부딪힌건지 체크해야됨 (현재위치랑 NextPos가 다른놈을 원래의 위치로 돌려놓기) if (OriginRPos != NextRPos) { NextRPos = OriginRPos; } else if (OriginBPos != NextBPos) { NextBPos = OriginBPos; } CanMove = true; break; } // 언제 그냥 break 되어야 하는가? 이미 방문했던 상황이거나, 이동이 종료되었을때 if (Visited[NextRPos.Y][NextRPos.X][NextBPos.Y][NextBPos.X]) { break; } Visited[NextRPos.Y][NextRPos.X][NextBPos.Y][NextBPos.X] = true; } // 더이상 이동할수 없었다면.. if (CanMove) { // 10회를 넘거나, 파란공이 구멍에 혼자 들어가거나, 구멍에서 두 구슬이 겹친적이 있거나. Fail if (NextTryNum > 10 || (NextBPos == HolePos && NextRPos != HolePos) || IsHoleOverlapped) { // 아직 queue에 남아있을때는 섣불리 종료해선안된다. if (PQ.empty() && i == 3) { cout << "-1"; return; } } // 빨간공만 구멍에 들어간다? succeed if (NextRPos == HolePos && NextBPos != HolePos && IsHoleOverlapped == false) { cout << NextTryNum; return; } if ((CurRPos != NextRPos || CurBPos != NextBPos) && IsHoleOverlapped == false) PQ.push({ NextRPos, NextBPos, NextTryNum }); } } } cout << "-1"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; Coord RPos; Coord BPos; for (int i = 1; i <= N; i++) { string Msg; cin >> Msg; for (int j = 1; j <= M; j++) { Map[i][j] = Msg[j-1]; if (Map[i][j] == 'O') { HolePos = Coord(i, j); } else if (Map[i][j] == 'R') { RPos = Coord(i, j); } else if (Map[i][j] == 'B') { BPos = Coord(i, j); } } } Game(RPos, BPos); return 0; }

제출 #89455

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: