구슬 탈출 2_13460

문제 출처 : 구슬탈출2_13460

파라미터 정리

빨간 구슬1, 1x1 -> 구멍으로 탈출 o
파란구슬 1, 1x1 -> 구멍으로 탈출 x
NxM, 보드의 크기 (N:세로, M:가로)
가장자리 행/열은 막혀져 있음
좌, 우, 상, 하 中 1가지 방향으로 구슬을 옮길 수 있음
최소 몇 번 만에 빨간 구슬을 빼낼 수 있는 지 반환
.: 빈칸
#: 벽
o: 구멍의 위치
R: 빨간 구슬의 위치
B: 파란 구슬의 위치
제한 사항
두 구슬은 동작을 실행했을 때 함께 적용되며 끝까지 움직임
두 구슬은 동시에 같은 칸에 있을 수 없음

간략한 과정

input_1 N,M 입력받기 (3~N,M~10)
input_2 NxM 행렬의 초기 상태 입력받기
상하좌우 탐색을 계속해서 시도함
구슬이 구멍을 지나가는 지 여부를 확인하는 함수 만들기
(구멍을 지나갈 경우 탈출했다고 간주함)
빨간 구슬이 탈출할 경우 시도한 횟수 return
파란 구슬이 탈출할 경우 INF return
시도 횟수 cnt 가 11이 될 경우 INF return
시도한 횟수의 최소값을 찾기(min 사용)
output 최소 몇 번 만에 빨간 구슬을 빼낼 수 있는 지 출력하기
최소값이 INF 일 경우 -1 return (11번 이상/불가능 -1을 출력)
최소값 return (10번 이내로 탈출 가능)

코드

#include <iostream>
#include <algorithm>

using namespace std;

#define INF 984561542

int N,M;
char Map[10][10];
pair<int, int> Red, Blue;
int res;
int Dr[4] = {0,1,0,-1};
int Dc[4] = {1,0,-1,0};

int Inverse(int n){
    if(n == 0) return 2;
    if(n == 1) return 3;
    if(n == 2) return 0;
    if(n == 3) return 1;
}

int moveDist(int r1, int c1, int r2, int c2){
    int dist = abs(r1-r2) + abs(c1-c2);
    return dist;
}

void move(int Rr, int Rc, int Br, int Bc, int cnt, int i){
    if(cnt > 10) return;
    if(cnt >= res) return;

    bool Rflag = false, Bflag = false;
    
    int nRr = Rr + Dr[i], nRc = Rc + Dc[i];
    while(1){
        if(Map[nRr][nRc] == '#') break;
        if(Map[nRr][nRc] == 'O'){
            Rflag = true;
            break;
        }
        nRr += Dr[i];
        nRc += Dc[i];
    }
    nRr -= Dr[i];
    nRc -= Dc[i];
    
    int nBr = Br + Dr[i], nBc = Bc + Dc[i];
    while(1){
        if(Map[nBr][nBc] == '#') break;
        if(Map[nBr][nBc] == 'O'){
            Bflag = true;
            break;
        }
        nBr += Dr[i];
        nBc += Dc[i];
    }
    nBr -= Dr[i];
    nBc -= Dc[i];
    
    if(Bflag) return;
    else if(Rflag){
            res = min(res, cnt);
            return;    
    }
    
    if(nRr == nBr && nRc == nBc){
        int Rdist = moveDist(Rr,Rc,nRr,nRc);
        int Bdist = moveDist(Br,Bc,nBr,nBc);
        if(Rdist > Bdist){
            nRr -= Dr[i];
            nRc -= Dc[i];
        }else{
            nBr -= Dr[i];
            nBc -= Dc[i];
        }
    }
    for(int k = 0; k < 4; k++){
        if(k == i) continue;
        if(k == Inverse(i)) continue;
        move(nRr, nRc, nBr, nBc, cnt+1, k);
    }
    return;
}

int solve(){
    res = INF;
    
    for(int i = 0; i < 4; i++){
        move(Red.first, Red.second, Blue.first, Blue.second, 1, i);
    }
    if(res == INF || res > 10) return -1;
    else return res;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
            if(Map[i][j] == 'R'){
                Red = make_pair(i,j);
                Map[i][j] = '.';
            }else if(Map[i][j] == 'B'){
                Blue = make_pair(i,j);
                Map[i][j] = '.';
            }
        }
    }
    
    cout << solve() << endl;

    return 0;
}

다른풀이

코드 좀더 간결하게

#include <iostream>
#include <algorithm>

using namespace std;

#define INF 98765443

struct loc{
    int r,c;
};

int N,M;
char map[10][10];
loc red,blue;
int res = INF;

int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};

int reverse(int i){
    return (i+2)%4;
}

void move(loc newRed, loc newBlue, int cnt, int i){
    if(cnt > 10) return;
    if(cnt >= res) return;
    
    int newRedR = newRed.r, newRedC = newRed.c;
    bool redFlag = false;
    int redDist = 0;
    while(1){
        newRedR += dr[i];
        newRedC += dc[i];
        redDist++;
        
        if(map[newRedR][newRedC] == '#'){
            newRedR -= dr[i];
            newRedC -= dc[i];
            redDist--;
            break;
        }else if(map[newRedR][newRedC] == 'O'){
            redFlag = true;
            break;
        }
    }
    
    int newBlueR = newBlue.r, newBlueC = newBlue.c;
    bool blueFlag = false;
    int blueDist = 0;
    while(1){
        newBlueR += dr[i];
        newBlueC += dc[i];
        blueDist++;
        
        if(map[newBlueR][newBlueC] == '#'){
            newBlueR -= dr[i];
            newBlueC -= dc[i];
            blueDist--;
            break;
        }else if(map[newBlueR][newBlueC] == 'O'){
            blueFlag = true;
            break;
        }
    }
    
    if(blueFlag)
        return;
    else if(redFlag){
        res = min(res,cnt);
        return;
    }
    
    if(newRedR == newBlueR && newRedC == newBlueC){
        if(redDist < blueDist){
            newBlueR -= dr[i];
            newBlueC -= dc[i];
        }else{
            newRedR -= dr[i];
            newRedC -= dc[i];
        }
    }
    
    for(int k = 0; k < 4; k++){
        if(i == k) continue;
        if(reverse(i) == k) continue;
        move({newRedR,newRedC}, {newBlueR,newBlueC}, cnt+1, k);
    }
    
    return;
}

int solve(){
    
    for(int i = 0; i < 4; i++){
        move(red, blue, 1, i);
    }
    
    if(res == INF) return -1;
    return res;
}

int main()
{
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M ; j++){
            cin >> map[i][j];
            if(map[i][j] == 'R'){
                red = {i,j};
                map[i][j] = '.';
            }
            else if(map[i][j] == 'B'){
                blue = {i,j};
                map[i][j] = '.';
            }
                
        }
    }
    
    cout << solve() << endl;
    
    return 0;
}