Codeforces Round #420 (Div. 2) D. Okabe and City

http://codeforces.com/contest/821/problem/D

\(n,m,k\le{10^4}\)

세로 n, 가로 m 인 n * m 크기의 격자판의 (1,1) 에서 (n,m) 까지 이동하고싶다.

격자판의 k개의 칸에는 불이 켜져있다. (1,1)은 무조건 켜져있다. 

이동할 때에는 무조건 불이 켜져있는 칸만 밟을 수가 있다.

하지만 코인 1개를 사용하면 한 행 전체, 혹은 한 열 전체의 불을 켤 수가 있다.

한번에 하나의 열 또는 행만 켤 수가 있으며 만약 불을 켜는 행이나 열을 바꾸고 싶다면

원래 부터 불이 켜져있던 칸으로 이동을 해야 한다. 물론 바꾸면 이전에 켠 행(열)은 

원래 켜져있던 칸을 빼고는 다 꺼지고 새로운 행(열)이 켜지며 또 코인 1개가 든다.

이 때 (1,1) 부터 (n,m) 까지가는데에 드는 최소 코인의 수를 구하여라. (만약 가는 것이 불가능하면 -1을 출력)

처음엔 코인을 사용하지 않아도 이동할 수 있는 칸들 끼리 유니온 파인드로 묶어준 뒤 bfs를 돌렸는데

구현을 잘 못했던 탓도 있지만 코드가 좀 더 길어져서 코인을 1개 사용해서 이동할 수 있는 칸들은

비용 1, 코인을 사용하지 않고도 이동할 수 있는 칸들은 비용 0으로 인접리스트로 그래프를 구성하여

다익스트라를 돌렸는데 MLE 가 나서 아예 그래프를 구성하지 않고 바로 다익스트라를 돌렸다.

O(n^2lgn) 정도라 꽤 큰수인데 시간 제한이 4초이고 실제로 돌리면 그렇게 오래걸리지 않는건지 0.5초정도가나온다.

이 문제에서 중요한 것은 두가지인데,

첫번째는 코인을 1개 사용해서 이동할 수 있는지 판별하는 기준이다.

두 점의 x좌표의 차이가 2이하이거나 y좌표의 차이가 2이하이면 된다.

두번째는 우리의 목적지가 (n,m) 인데 만약 (n,m) 이 처음에 불이 켜져있지 않는 경우엔 어떻게 처리하냐이다.

코인을 1개 사용하여 (n,m) 으로 갈 수 있는 칸들의 목록을 가지고 있다가 마지막에 반복문돌리면서

그 칸들까지 오는 거리 + 1 로 답을 갱신해 주면된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct point{
    int pi, pj;
};
int N,M,K;
point points[10003];
int dist[10003];
vector<int> endable;
vector<pair<int,int> > G[10003];
int S,T;
bool isDist1(point A, point B){
    if(A.pi == B.pi && abs(A.pj - B.pj) == 1) return true;
    if(A.pj == B.pj && abs(A.pi - B.pi) == 1) return true;
    return false;
}
bool isDist2(point A, point B){
    return abs(A.pi - B.pi) <= 2 || abs(A.pj - B.pj) <= 2;
}
int main() {
    T = 10002;
    cin >> N >> M >> K;
    for(int i = 0 ; i < K; i++){
        int pi,pj;
        cin >> pi >> pj;
        if(pi >= N-1 || pj >= M-1) endable.push_back(i);
        if(pi == N && pj == M) T = i;
        if(pi == 1 && pj == 1) S = i;
        points[i] = point{pi, pj};
    }
    memset(dist,0x3c,sizeof(dist));
    priority_queue<pair<int,int> > pq;
    pq.push({0,S});
    dist[S] = 0;
    while(!pq.empty()){
        int here = pq.top().second;
        int curD = -pq.top().first;
        pq.pop();
        if(dist[here] < curD) continue;
        for(int there = 0 ; there < K; there++){
            auto p = points[there];
            int cost = inf;
            if(isDist1(points[here], points[there])) cost = 0;
            else if(isDist2(points[here], points[there])) cost = 1;
            if(dist[there] > dist[here] + cost) {
                dist[there] = dist[here] + cost;
                pq.push({-dist[there], there});
            }
        }
    }
    int ans = dist[T];
    for(int node : endable) ans = min(ans, dist[node] + 1);
    if(ans == inf) cout << -1;
    else cout << ans;
    return 0;
}