CF 677 D - Vanya and Treasure
問題
問題概要
のグリッドとして表される宮殿の中にいる.それぞれの部屋の中には引き出しがあり,上から行左から列の位置には番の引き出しがある.番の引き出しには,番の引き出しを開けるためのカギが入っており,番の引き出しは鍵がかかっていない(引き出しには〜番まで種類の引き出しがある).そして,番の引き出しには宝物が入っている.
左上をスタート地点として,4近傍に移動する事ができる.宝物を手に入れるまでに必要な最小の移動回数を求めよ.
アイデア
dp[y][x] = 位置(x,y)にある引き出しを開けるのにかかる最小時間
として,考えていくことにしよう.このように設定しておくと,「今何番目の引き出しまで開けたかということは気にする必要がない(そのマスにある引き出しが何番なのかはすぐわかるから,その手前まで分かってればいい).
1番目の引き出しについては,左上からの最短距離なのでとなる.
次に番目の引き出しに関しては,番目の引き出しがあるマスをながめて,そこからの移動を考える.すると, と更新していくことが出来る.
ただし,これは同じような色が多くなってくると,単純に計算するのは無理になる(計算量がで間に合わない).
そこで次のような境界を設けて使い分けていく.
番目の引き出しの個数をとして,となった時には,番目の引き出しに関してはBFSによって最短距離をもとめることにする.この数が大きくなるということは,どちらもグリッド上に多く存在することになるので,BFSで比較的早く見つけられる.これをさっきのDP更新と使い分けていくことによって計算量を落とせる(計算量はとなる).
実装(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; }