白虎運送

問題 パソコン甲子園2008 12

下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。

トラックは東西南北方向の交差点に進入できるが、来た方向へはＵターンできない。さらに、交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる（赤と青のみ）。交差点に進入できるのは進行方向の信号機が青の場合である。また、交差点から隣の交差点への移動には一定の時間D分を要するが、渋滞の道路ではさらにd分要する。工事中で通れない道路もある。

N, M <= 20 であり、トラックは100分以内で目的地に到達できるものとする。

解説

最短経路問題なので、ダイクストラのアルゴリズムで解けそうですが、この問題の場合、以下のような状態空間を定義すれば、深さ優先探索で解くことができます。

V[y][x][t][d]: dの方向から交差点(y, x)に時刻tで到達することができれば、V[y][x][t][d] がtrueであるような４次元配列

トラックは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 }