読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Codeforces Round #355 (Div. 2) D. Vanya and Treasure

問題
Problem - D - Codeforces
n\times mの部屋があり,それぞれ宝箱が置いてある.タイプxの宝箱にはタイプx+1の宝箱を開ける鍵が入っている.タイプpの宝箱を開けるまでに移動する最小距離はいくつか.

解法
単純にタイプごとにダイクストラを行っていたら間に合わない.そこでタイプxの宝箱がある位置を配列で持っておき,タイプxからタイプx+1の全組み合わせを列挙して最小距離を求める.しかし,最悪の場合\left(\frac{nm}{2}\right)^2の組み合わせがあるのでこれもまた間に合わない.[タイプxの数\timesタイプx+1の数]が一定以上になったらダイクストラで探索をすることで最悪の場合を回避できる.

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int dist2[300][300];
int dist[300][300];
int a[300][300];
vector<pair<int,int>> chest[90001];

int main(void) {
    int i, j, n, m, p, t;
    cin >> n >> m >> p;
    rep (i,n) rep (j,m) {
        cin >> a[i][j];
        chest[a[i][j]].push_back(make_pair(i,j));
        if (a[i][j] == 1)
            dist[i][j] = i+j;
        else
            dist[i][j] = INF;
    }
    REP (t,2,p) {
        if (chest[t].size() * chest[t-1].size() < 1000000) for (auto p : chest[t]) for (auto q : chest[t-1])
            dist[p.first][p.second] = min(dist[p.first][p.second],dist[q.first][q.second]+abs(p.first-q.first)+abs(p.second-q.second));
        else {
            priority_queue<pair<int,pair<int,int>>> q;
            for (auto p : chest[t-1]) q.push(make_pair(-dist[p.first][p.second],p));
            rep (i,n) rep (j,m) {
                if (a[i][j] == t-1)
                    dist2[i][j] = dist[i][j];
                else
                    dist2[i][j] = INF;
            }
            while (!q.empty()) { 
                int d = -q.top().first + 1;
                int x = q.top().second.first;
                int y = q.top().second.second;
                q.pop();
                int dxy[4] = {-1,0,1,0};
                rep (i,4) {
                    int nx = x + dxy[i];
                    int ny = y + dxy[(i+1)%4];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (dist2[nx][ny] > d) {
                        dist2[nx][ny] = d;
                        q.push(make_pair(-d,make_pair(nx,ny)));
                    }
                }
            }
            rep (i,n) rep (j,m) if (a[i][j] == t)
                dist[i][j] = dist2[i][j];
        }
    }
    cout << dist[chest[p][0].first][chest[p][0].second] << endl;
    return 0;
}