白虎運送
2008.11.19 09:49 パソコン甲子園 2008
問題 パソコン甲子園2008 12
下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。
トラックは東西南北方向の交差点に進入できるが、来た方向へはUターンできない。さらに、交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる(赤と青のみ)。交差点に進入できるのは進行方向の信号機が青の場合である。また、交差点から隣の交差点への移動には一定の時間D分を要するが、渋滞の道路ではさらにd分要する。工事中で通れない道路もある。
N, M <= 20 であり、トラックは100分以内で目的地に到達できるものとする。
下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。

N, M <= 20 であり、トラックは100分以内で目的地に到達できるものとする。
解説
最短経路問題なので、ダイクストラのアルゴリズムで解けそうですが、この問題の場合、以下のような状態空間を定義すれば、深さ優先探索で解くことができます。
V[y][x][t][d]: dの方向から交差点(y, x)に時刻tで到達することができれば、V[y][x][t][d] がtrueであるような4次元配列
トラックは100分以内で目的地に到達できるので、t <= 100 であり、メモリも間に合います。
目的地の座標 (y, x) について、Vの値が最初に true となる t の値が答えになります。
サンプルプログラム
001 #include<iostream> 002 using namespace std; 003 004 #define REP(i, n) for ( int i = 0; i < (int)n; i++ ) 005 #define GMAX 20 006 #define TMAX 100 007 #define INFTY (1<<21) 008 009 int N, M, D, sy, sx, gy, gx; 010 int G[GMAX][GMAX][GMAX][GMAX], S[GMAX][GMAX]; 011 bool V[GMAX][GMAX][TMAX+1][4]; 012 013 static const int dy[4] = {0, -1, 0, 1}; 014 static const int dx[4] = {1, 0, -1, 0}; 015 016 bool valid( int y , int x ){ 017 return ( 0 <= y && 0 <= x && y < N && x < M ); 018 } 019 020 void dfs( int y, int x, int t, int d ){ 021 V[y][x][t][d] = true; 022 023 int ny, nx, nt; 024 for ( int nd = 0; nd < 4; nd++ ){ 025 if ( (d+2)%4 == nd ) continue; 026 027 ny = y + dy[nd]; 028 nx = x + dx[nd]; 029 030 if ( !valid(ny, nx) ) continue; 031 if ( G[y][x][ny][nx] == INFTY ) continue; 032 033 nt = t + G[y][x][ny][nx]; 034 035 if ( nt > TMAX ) continue; 036 037 if ( S[ny][nx] > 0 ){ 038 if ( nd % 2 == 0 ){ 039 if ( (nt/S[ny][nx])%2 != 1 ) continue; 040 } else { 041 if ( (nt/S[ny][nx])%2 != 0 ) continue; 042 } 043 } 044 045 if ( V[ny][nx][nt][nd] ) continue; 046 047 dfs( ny, nx, nt, nd ); 048 } 049 } 050 051 int compute(){ 052 REP(y, N) REP(x, M) REP(t, TMAX+1) REP(d, 4) V[y][x][t][d] = false; 053 REP(d, 4) dfs( sy, sx, 0, d ); 054 055 REP(t, TMAX+1) REP(d, 4) if ( V[gy][gx][t][d] ) return t; 056 } 057 058 int getNumber( char ch ){ return ch - 'a';} 059 060 bool input(){ 061 cin >> N >> M; 062 if ( N == 0 && M == 0 ) return false; 063 cin >> D; 064 065 int ny, nx; 066 REP(y, N) REP(x, M){ 067 S[y][x] = 0; 068 REP(nd, 4){ 069 ny = y + dy[nd]; 070 nx = x + dx[nd]; 071 if ( valid(ny, nx) ){ 072 G[y][x][ny][nx] = G[ny][nx][y][x] = D; 073 } 074 } 075 } 076 077 int nsignal, nconst, njam, y1, x1, y2, x2, k, d; 078 char ch, tmp; 079 080 cin >> nsignal; 081 for ( int i = 0; i < nsignal; i++ ){ 082 cin >> ch >> tmp >> x1 >> k; x1--; 083 S[getNumber(ch)][x1] = k; 084 } 085 086 cin >> nconst; 087 for ( int i = 0; i < nconst; i++ ){ 088 cin >> ch >> tmp >> x1; x1--; 089 y1 = getNumber(ch); 090 cin >> ch >> tmp >> x2; x2--; 091 y2 = getNumber(ch); 092 G[y1][x1][y2][x2] = G[y2][x2][y1][x1] = INFTY; 093 } 094 095 cin >> njam; 096 for ( int i = 0; i < njam; i++ ){ 097 cin >> ch >> tmp >> x1; x1--; 098 y1 = getNumber(ch); 099 cin >> ch >> tmp >> x2 >> d; x2--; 100 y2 = getNumber(ch); 101 G[y1][x1][y2][x2] += d; 102 G[y2][x2][y1][x1] += d; 103 } 104 105 cin >> ch >> tmp >> sx; sy = getNumber(ch); 106 cin >> ch >> tmp >> gx; gy = getNumber(ch); 107 sx--; gx--; 108 return true; 109 } 110 111 int main(){ 112 while( input() ) cout << compute() << endl; 113 return 0; 114 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |