함정에 빠진 이동관 - CyberFlower Algorithm

2019 KCPC 함정에 빠진 이동관 (신입생 부문 E번 / 일반 부문 A번) 코드 제출 url

제가 낸 문제입니다! 숭고한 대회때는 조금 challenging한 문제를 냈던 데 반해 이번에는 조금 well-known한 문제를 만들었습니다. :)

BFS 알고리즘을 이용하면 쉬운 문제입니다. BFS 알고리즘의 특성상 BFS 탐색 한 번으로 가중치가 1인 그래프에서 최단거리와 도달 여부를 모두 알 수 있습니다.

BFS 알고리즘에 대한 설명은 빠른 시일 내로 추가하도록 하겠습니다.

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int SZ=1005;
int arr[SZ][SZ];
int vst[SZ][SZ];
queue<pair<int,int>> q;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>arr[i][j];
    }
    int x,y; cin>>x>>y;
    memset(vst,-1,sizeof(vst));
    vst[1][1]=0;
    q.push({1,1});
    while(!q.empty()){
        auto h=q.front(); q.pop();
        if(h.ff==x && h.ss==y){
            cout<<vst[x][y];
            return 0;
        }
        for(int i=0;i<4;i++){
            int nx=h.ff+arr[h.ff][h.ss]*dx[i];
            int ny=h.ss+arr[h.ff][h.ss]*dy[i];
            if(nx<1 || nx>n) continue;
            if(ny<1 || ny>m) continue;
            if(vst[nx][ny]!=-1) continue;
            vst[nx][ny]=vst[h.ff][h.ss]+1;
            q.push({nx,ny});
        }
    }
    if(vst[x][y]!=-1) cout<<vst[x][y];
    else cout<<-1;
    return 0;
}

2019 KCPC trap