白虎運送
2008.11.19 09:49 パソコン甲子園 2008
問題 パソコン甲子園2008 12
下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。
トラックは東西南北方向の交差点に進入できるが、来た方向へはＵターンできない。さらに、交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる（赤と青のみ）。交差点に進入できるのは進行方向の信号機が青の場合である。また、交差点から隣の交差点への移動には一定の時間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であるような４次元配列
トラックは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) | ↑ページトップ |