NYPC 2021 예선 | K-좀비

[문제]

 

우니는 놀이공원에 있는 좀비 어트랙션에 들어가게 되었다. 좀비 어트랙션은 N개 행과 M개 열의 격자로 이루어져 있다. 우니는 처음에 격자의 왼쪽 위인 1번째 행, 1번째 열 격자 칸에서 시작해서, 격자의 오른쪽 아래인 N번째 행, M번째 열 격자 칸까지 가려고 한다. 우니는 현재 있는 칸에서 위, 아래, 왼쪽, 오른쪽 칸 중 하나로 움직일 수 있다. 우니는 좀비 때문에 겁에 질려있기 때문에, 움직이지 않고 가만히 있을 수는 없다. 한 칸을 움직이는 데는 1의 시간이 걸리며, 처음에는 시각 0으로 시작한다. 즉, 현재 시각은 지금까지 움직인 횟수와 같다.

좀비 어트랙션의 각 격자 칸은 다음 중 하나이다.

• 빈칸: 우니가 자유롭게 오갈 수 있는 격자 칸이다.
• 벽: 우니가 오갈 수 없는 격자 칸이다.
• K-좀비: 주기가 K인 좀비이다. (2≤K≤9)
  • 우니는 K-좀비가 있는 격자 칸으로 오갈 수 없다.
  • 시각이 K의 배수가 아니면, K-좀비가 있는 격자 칸에 상하좌우로 인접한 칸에는 갈 수 없다.

우니가 오른쪽 아래 칸으로 움직여서 좀비 어트랙션에서 빠져나오는 것을 도와주자!

 

 

[입력 형식]

 

첫 줄에 N과 M이 공백으로 구분되어 주어진다. (1≤N, M≤25)

다음 N개의 줄에는 길이 M의 문자열이 주어진다. 이중 i번째 줄의 j번째 문자는 다음을 의미한다.

• . : i 번째 행, j번째 열에 해당하는 격자 칸은 빈칸이다.
• # : i번째 행, j번째 열에 해당하는 격자 칸은 벽이다.
• 2~9 : i번째 행, j번째 열에 해당하는 격자 칸은 주기 K가 입력으로 주어진 문자에 해당하는 K-좀비이다.

 

[출력 형식]

 

문제의 조건을 만족하면서 우니가 오른쪽 아래 칸으로 가는 이동 커맨드를 나타내는 문자열을 출력하여라. 문자열의 길이는 100 000 이하이고, 각 문자는 UDLR 중 하나로 이루어져 있어야 한다. 가능한 답이 여럿일 경우, 아무것이나 하나 출력한다. 문자열의 길이가 가능한 것 중 최소일 필요는 없다.

문자열의 i번째 문자는 다음을 의미한다.

• U : 시각 i−1에서 우니가 한 칸 위로 움직였다.
• D : 시각 i−1에서 우니가 한 칸 아래로 움직였다.
• L : 시각 i−1에서 우니가 한 칸 왼쪽으로 움직였다.
• R : 시각 i−1에서 우니가 한 칸 오른쪽으로 움직였다.

우니가 이동하는 동안 움직일 수 없는 칸으로 가서는 안 되고, 최종적으로 오른쪽 아래 칸에 있어야 한다.

주어지는 모든 입력에서, 우니가 항상 오른쪽 아래 격자 칸으로 이동해서 좀비 어트랙션을 빠져나가는 길이 100 000 이하의 이동 커맨드를 나타내는 문자열이 있음이 보장된다.

 

 

[해설]

 

정점을 (시간, x좌표, y좌표)로 두고 BFS를 돌리면 문제를 해결할 수 있습니다.

 

 

[C/C++ 코드]

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
int n,m,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char arr[26][26];
bool visited[MAX][26][26];
pair<int,pair<int,int>>p[MAX][26][26];

bool f(int w,int x,int y){
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
		int ny=y+dy[i];
        if(arr[nx][ny]>='2'&&arr[nx][ny]<='9'){
            int tmp=arr[nx][ny]-'0';
            if(w%tmp){
            	return false;
			}
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    fill(arr[0],arr[26]+26,'#');
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i][m+1]='#';
    }
    queue<pair<int,pair<int,int>>>q;
    q.emplace(0,make_pair(1,1));
    visited[0][1][1]=true;
    int t=0;
    while(!q.empty()){
        auto it=q.front();
		q.pop();
        int x = it.second.first, y = it.second.second;
        for (int k=0;k<4;k++){
            int nx = x+dx[k], ny = y+dy[k];
            if (arr[nx][ny]=='#' || (arr[nx][ny]>='2' && arr[nx][ny]<='9')) continue;
            if (!f(it.first+1, nx, ny)) continue;
            if (visited[it.first+1][nx][ny]) continue;
            visited[it.first+1][nx][ny] = 1;
            p[it.first+1][nx][ny] = it;
            q.emplace(it.first+1, make_pair(nx, ny));
            if (nx==n && ny==m){
                t = it.first+1; break;
            }
        }
        if (t) break;
    }

    string result;
    pair<int,pair<int, int>>cur={t,make_pair(n,m)};
    while(true){
    	if(!cur.first){
    		break;
		}
		auto w=p[cur.first][cur.second.first][cur.second.second];
        if(w.second.first-cur.second.first==1){
        	result.push_back('U');
		}
        else if(w.second.first-cur.second.first==-1){
        	result.push_back('D');
		}
        else if(w.second.second-cur.second.second==1){
        	result.push_back('L');
		}
        else{
        	result.push_back('R');
		}
        cur=w;
	}
    reverse(result.begin(),result.end());
    cout<<result<<'\n';
}