abc 020 C - 壁抜け
問題概要
省略
解法
2分探索and最短経路問題。
xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダイクストラを使い、スタートからゴールまでの最短距離を求めて、t以下であるかを確認して、2分探索に利用していけばいい。
また、bfsでも解くことができる。
used[y][x][i] := (y,x)に#をi回通ってきた時の最短距離
として、普通のbfsに対して、状態数を一つ増やして、値を記録していけばいい。これは、#の時と.の時でパスの長さが異なるため、任意の地点までの最短経路が、任意の地点までに来るまでに通った#の数によって変わってくるからである.
ダイクストラとbfsの違い
基本的にやっていることは同じ. パスがコストが異なる条件を考えた時に、ダイクストラの場合, 任意のマスを見た地点でそのマスの最短経路が決まるが, bfsの場合, パスの本数として近いものから見ていくだけであるので, パスの距離が異なると, queueから初めに取り出したものがそのマスへの最短距離とは限らないので、マスの座標だけでなく, 新たに他の状態を持たせて考えなければならない.
ミス
はじめ、普通に、bfsを書こうとしていた。しかし、"#“の時は、1マス分の動きが”.“と異なるため、普通にbfsをして、一度調べた部分はもう調べなくても、すでに、最短経路が求まっているというふうにはいかない。1マス分の移動コストが異なるため、なんども最短経路が更新される可能性があるので、ダイクストラで実装する必要がある。と思ったけど、bfsでもできた。
コード
#include <iostream> #include <cstdio> #include <queue> #include <tuple> #include <vector> #include <algorithm> using namespace std; typedef long long ll; typedef tuple<ll, int, int> T; #define rep(i,n) for(int i=0;i<(n);i++) const ll INF = 1e9; int h, w, t; string s[12]; int sy, sx, gy, gx; int dy[] = {1, 0, 0, -1}; int dx[] = {0, 1, -1, 0}; bool dijkstra(int m){ ll memo[12][12]; rep(i, 12)rep(j, 12)memo[i][j] = INF * 10;//mより大きな値で初期化しておかないと priority_queue<T, vector<T>, greater<T> > q; q.push(make_tuple(0, sy, sx)); memo[sy][sx] = 0; while(!q.empty()){ ll c; int y, x; tie(c, y, x) = q.top(); q.pop(); rep(i, 4){ int ny = y + dy[i], nx = x + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(s[ny][nx] == '#'){ if(memo[ny][nx] > c + m){//最小値が更新 memo[ny][nx] = c + m; q.push(make_tuple(c + m, ny, nx)); } }else{//最小値を更新 if(memo[ny][nx] > c + 1){ memo[ny][nx] = c + 1; q.push(make_tuple(c + 1, ny, nx)); } } } } if(memo[gy][gx] <= t) return true; else return false; } int main(void){ cin >> h >> w >> t; rep(i, h) cin >> s[i]; rep(i, h)rep(j, w){ if(s[i][j] == 'S'){ sy = i; sx = j; }else if(s[i][j] == 'G'){ gy = i; gx = j; } } ll l = 1, r = INF; while(r - l > 1){ int x = (l + r) / 2; if(dijkstra(x)) l = x; else r = x; } printf("%d\n", l); return 0; }
bfs
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int h, w; ll t; pair<int, int> S, G; string s[12]; bool bfs(int m){//m := #に行く時のコスト queue<tuple<int, int, ll, int>> q; //used[y][x][i] := (y,x)に#をi回通ってきた時の最短距離 ll used[12][12][110]; rep(i, 12)rep(j, 12)rep(k, 110)used[i][j][k] = INFF; q.push(make_tuple(S.fi, S.se, 0, 0)); used[S.fi][S.se][0] = 0;//start while(!q.empty()){ int y, x, black; ll cost; tie(y, x, cost, black) = q.front(); q.pop(); rep(i, 4){ int ny = y + dy[i], nx = x + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; ll ncost = cost + (s[ny][nx] == '#' ? m : 1); int nblack = black + (s[ny][nx] == '#' ? 1 : 0); if(used[ny][nx][nblack] != INFF) continue; used[ny][nx][nblack] = ncost;//(ny,nx)に#をnblack回通って、最短距離ncostで来れたことを記録 if(ny == G.fi && nx == G.se) continue;//goal q.push(make_tuple(ny, nx, ncost, nblack)); } } rep(i, 110){//t以下でgoalに他取り付いているものがあるか調べる if(used[G.fi][G.se][i] <= t) return true; } return false; } int main(void){ cin >> h >> w >> t; rep(i, h) cin >> s[i]; rep(i, h)rep(j, w){ if(s[i][j] == 'S') S.fi = i, S.se = j; if(s[i][j] == 'G') G.fi = i, G.se = j; } int l = 0, r = INF; while(r - l > 1){//2分探索 int m = (l + r) / 2; if(bfs(m)) l = m; else r = m; } printf("%d\n", l); return 0; }
