問題

問題概要

$n*m$ のグリッドとして表される宮殿の中にいる．それぞれの部屋の中には引き出しがあり，上から $i$ 行左から $j$ 列の位置には $a_{i,j}$ 番の引き出しがある． $x( \le p-1)$ 番の引き出しには， $x+1$ 番の引き出しを開けるためのカギが入っており， $1$ 番の引き出しは鍵がかかっていない(引き出しには $1$ 〜 $p$ 番まで $p$ 種類の引き出しがある)．そして， $p$ 番の引き出しには宝物が入っている．

左上をスタート地点として，4近傍に移動する事ができる．宝物を手に入れるまでに必要な最小の移動回数を求めよ．

$1 \le n,m \le 300$
$1 \le p \le n*m$

アイデア

dp[y][x] = 位置(x,y)にある引き出しを開けるのにかかる最小時間として，考えていくことにしよう．このように設定しておくと，「今何番目の引き出しまで開けたかということは気にする必要がない(そのマスにある引き出しが何番なのかはすぐわかるから，その手前まで分かってればいい)．

1番目の引き出しについては，左上からの最短距離なので $dp_{y,x} =x+y$ となる．

次に $b (\ge 2)$ 番目の引き出しに関しては， $b-1$ 番目の引き出しがあるマスをながめて，そこからの移動を考える．すると， $dp_{y,x} = min \{ dp_{y1,x1} + abs(x-x1) + abs(y-y1) \} (a_{y1,x1} = b-1)$ と更新していくことが出来る．

ただし，これは同じような色が多くなってくると，単純に計算するのは無理になる(計算量が $O(n^2 m^2)$ で間に合わない)．

そこで次のような境界を設けて使い分けていく．

$i$ 番目の引き出しの個数を $ct_i$ として， $ct_i * ct_{i-1} \ge n*m$ となった時には， $i$ 番目の引き出しに関してはBFSによって最短距離をもとめることにする．この数が大きくなるということは，どちらもグリッド上に多く存在することになるので，BFSで比較的早く見つけられる．これをさっきのDP更新と使い分けていくことによって計算量を落とせる(計算量は $O(nm \sqrt{nm} )$ となる)．

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

const int INF=123456789;
int n,m;

inline bool in(int x, int y)
{
    return(0<=x && x<m && 0<=y && y<n);
}

int main()
{
    int P;
    int a[300][300];
    int ct[90000]={0};

    //i番の引き出しの位置を記録
    vector<pi> num[90000];

    cin >>n >>m >>P;
    rep(i,n)rep(j,m)
    {
        scanf(" %d", &a[i][j]);
        //0-indexedに揃える
        --a[i][j];

        num[a[i][j]].pb(pi(i,j));
        ++ct[a[i][j]];
    }

    int dp[300][300];
    fill(dp[0],dp[300],INF);

    //まず0の位置のdpを更新しておく
    for(const auto &p:num[0]) dp[p.fi][p.se] = p.fi+p.se;

    for(int b=1; b<P; ++b)
    {
        if(ct[b]*ct[b-1] >= n*m)
        {
            int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

            //BFS
            int d[300][300];
            fill(d[0],d[300],INF);
            queue<pi> que;
            for(const auto &p: num[b-1])
            {
                que.push(p);
                d[p.fi][p.se]=dp[p.fi][p.se];
            }

            while(!que.empty())
            {
                pi v=que.front();
                que.pop();
                rep(i,4)
                {
                    int nx=v.se+dx[i], ny=v.fi+dy[i];
                    if(in(nx,ny) && d[ny][nx]>d[v.fi][v.se]+1)
                    {
                        d[ny][nx] = d[v.fi][v.se]+1;
                        que.push(pi(ny,nx));
                    }
                }
            }

            for(const auto &p:num[b]) dp[p.fi][p.se]=d[p.fi][p.se];
        }
        else
        {
            //ループでDP更新
            for(const auto &p:num[b])
            {
                for(const auto &q:num[b-1])
                {
                    dp[p.fi][p.se] = min(dp[p.fi][p.se], dp[q.fi][q.se]+abs(p.fi-q.fi)+abs(p.se-q.se));
                }
            }
        }
    }

    int ans=INF;
    for(const auto &p:num[P-1]) ans=min(ans, dp[p.fi][p.se]);
    cout << ans << endl;
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 677 D - Vanya and Treasure

問題

問題概要

アイデア

実装(C++)