[SWEA] 7793. 오! 나의 여신님

 

문제를 읽어보면 그냥 BFS+시뮬레이션으로 풀면 될거같다

심지어 크기도 작다!!

 

악마->수연  이 순서대로 보내면 수연이가 갈 수 있는곳의 최단거리를 BFS로 구할 수 있다!

 

큐를 2개만들고 악마큐를 먼저 실행시키고, 수연이큐를 실행시키자

악마가 다음칸으로 갈 수 있는 조건은 .이거나 S이거나이고

수연이가 갈수있는 조건은 .이거나 D이다!

 

악마가 방문할때마다 *로 바꿔주고 수연이가 방문할때마다 S로 바꿔주면 

답이 착하게 나온다!!

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m; 
char arr[55][55];
int dist[55][55];
bool check[55][55];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
int Sx,Sy,Dx,Dy;
int main(){
    int t; scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        scanf(" %d %d",&n,&m);
        memset(check,0,sizeof(check));
        memset(dist,0,sizeof(dist));
        queue<pair<int,int>> su,de;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf(" %1c",&arr[i][j]);
                if(arr[i][j]=='S') Sx=i,Sy=j;
                else if(arr[i][j]=='D') Dx=i,Dy=j;
                else if(arr[i][j]=='*') {
                    de.push({i,j});
                    check[i][j]=true;
                }
            }
        }
        su.push({Sx,Sy});
        check[Sx][Sy]=true;
        while(!su.empty()){
            int s = de.size();
            while(s>0 && s--){
                int x = de.front().first;
                int y = de.front().second;
                de.pop();
                for(int i=0;i<4;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && ((!check[nx][ny] && arr[nx][ny]=='.') || (check[nx][ny] && arr[nx][ny]=='S'))){
                        check[nx][ny]=true;
                        arr[nx][ny]='*';
                        de.push({nx,ny});
                    }
                }
            }
            s=su.size();
            while(s>0 && s--){
                int x = su.front().first;
                int y = su.front().second;
                su.pop();
                arr[x][y]='.';
                for(int i=0;i<4;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && !check[nx][ny] && (arr[nx][ny]=='.' || arr[nx][ny]=='D')){
                        check[nx][ny]=true;
                        arr[nx][ny]='S';
                        dist[nx][ny]=dist[x][y]+1;
                        su.push({nx,ny});
                    }
                }
            }
        }
        printf("#%d ",tc);
        if(dist[Dx][Dy]==0) puts("GAME OVER");
        else printf("%d\n",dist[Dx][Dy]);
    }
}