3055_탈출

링크 https://www.acmicpc.net/problem/3055

3055번: 탈출

접근

 물과의 상호작용을 확인 하면서

 비버굴로 들어가기 위한 최소 거리 도출

 

 이동조건

 고슴도치

    영역이내

    돌이 아님

    물이 차오르지 않을 예정

 물

    돌이 아님

    비버의 소굴이 아님

 

 3차원 배열로 시간 증가에 따른 물의 흐름을 저장한다

 깊이가 깊어질 수록 시간과 침범 영역이 증가 한다

 

 탐색을 진행하는 구조체에도 시간을 나타내는 변수를 저장한다

 현재 시간의 위치에서 물에 닿지 않고

 다음 시간의 위치에서도 물에 닿지 않는다면

 탐색을 진행 한다

 

#include <iostream>
#include <queue>
#include <vector>

#define MAX 51
#define WATER '*'
#define ROCK 'X'
#define EMPTY '.'
#define CHARACTER 'S'
#define EXIT 'D'
#define DANGER 'R'

using namespace std;

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

struct pos{int y, x, t;};

char map[MAX*MAX][MAX][MAX];
int dist[MAX][MAX];
int r, c;

void spread(int idx){
    int ny, nx;
    for(int y = 0 ; y < MAX ; y++){
        for(int x = 0 ; x < MAX ; x++){
            if(map[idx][y][x] != WATER) continue;
            map[idx+1][y][x] = WATER;
            for(int i = 0 ; i < 4; i++){
                ny = y + dy[i]; nx = x + dx[i];
                if(ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
                if(map[0][ny][nx] == EXIT || map[0][ny][nx] == ROCK) continue;
                map[idx+1][ny][nx] = WATER;
            }
        }
    }
}

void spreadAll(){
    for(int i = 0 ; i < MAX*MAX -1 ; i++){
        spread(i);
    }
}

int bfs(pos start, pos end){
    int ny, nx;
    queue<pos> q;
    dist[start.y][start.x] = 1;
    q.push(start);
    
    while(!q.empty()){
        pos s = q.front();
        q.pop();
        
        if(s.y == end.y && s.x == end.x){
            return dist[s.y][s.x] -1;
        }
        
        for(int i = 0 ; i < 4; i++){
            ny = s.y + dy[i]; nx = s.x + dx[i];
            if(ny < 0 || ny >= r || nx<0 || nx>=c ) continue;
            if(map[s.t][ny][nx] == WATER || map[s.t+1][ny][nx] == WATER) continue;
            if(dist[ny][nx] > 0 || map[0][ny][nx] == ROCK) continue;
            dist[ny][nx] = dist[s.y][s.x] + 1;
            q.push({ny, nx, s.t + 1});
        }

        
    }
    return -1;
}


int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    pos start, end;
    
    cin>>r>>c;
    for(int y = 0 ; y < r; y++){
        for(int x = 0 ; x< c ; x++){
            cin>>map[0][y][x];
            if(map[0][y][x] == CHARACTER){
                start = {y, x, 0};
            }else if(map[0][y][x] == EXIT){
                end = {y, x, 0};
            }
        }
    }
    
    spreadAll();
    int ret = bfs(start, end);
    
    if(ret == -1){
        cout<<"KAKTUS"<<endl;
    }else{
        cout<<ret<<endl;
    }
    
    
    
    return 0;
}