Manhattan Wiring
2007.09.02 00:45 ACM/ICPC 2006
[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem E
[難易度] ★★★★
[解説]
深さ優先探索 + 枝狩り + 幅優先探索
まず、深さ優先探索(バックトラック)で、2と2を繋ぐパスを探します(総当り)。
パスを探す過程で、例えば以下のような「無駄な」あるいは「ありえない」部分パスを発見したら枝を刈ります。
などなど、、.(ここまで刈ればPOJでも受理されます)
2と2を繋ぐパスを発見したときに、3と3を繋ぐ最短パスを幅優先探索で求め、最小値を更新していきます。
[サンプルプログラム]
[難易度] ★★★★
[解説]
深さ優先探索 + 枝狩り + 幅優先探索
まず、深さ優先探索(バックトラック)で、2と2を繋ぐパスを探します(総当り)。
パスを探す過程で、例えば以下のような「無駄な」あるいは「ありえない」部分パスを発見したら枝を刈ります。
22 22ワイヤーが接してしまう場合
202 222これらの回転
2002 2222これらの回転
*000..00* 2000..002 2222..222これらの回転
などなど、、.(ここまで刈ればPOJでも受理されます)
2と2を繋ぐパスを発見したときに、3と3を繋ぐ最短パスを幅優先探索で求め、最小値を更新していきます。
[サンプルプログラム]
001 #include<iostream> 002 #include<queue> 003 #include<algorithm> 004 using namespace std; 005 #define INFTY (1<<15) 006 #define MAX 9 007 #define EMPTY '0' 008 #define OBSTACLE '1' 009 #define TWO '2' 010 #define THREE '3' 011 012 class Point{ 013 public: 014 int i, j; 015 Point(){} 016 Point( int i , int j ): i(i), j(j){} 017 bool operator == ( const Point &p ) const{ 018 return i == p.i && j == p.j; 019 } 020 }; 021 022 int N, M; 023 char G[MAX+2][MAX+2]; 024 Point two[2], three[2]; 025 int mincost; 026 static const int di[4] = {0, -1, 0, 1}; 027 static const int dj[4] = {1, 0, -1, 0}; 028 029 int bfs(){ 030 int D[MAX+2][MAX+2]; 031 queue<Point> Q; 032 033 for ( int i = 1; i <= N; i++ ){ 034 for ( int j = 1; j <= M; j++ ) D[i][j] = INFTY; 035 } 036 037 Q.push(Point(three[0].i, three[0].j)); 038 D[three[0].i][three[0].j] = 0; 039 040 Point u, v; 041 int ni, nj; 042 while(!Q.empty()){ 043 u = Q.front(); Q.pop(); 044 if ( u== three[1] ) return D[u.i][u.j]; 045 for ( int d = 0; d < 4; d++ ){ 046 ni = u.i + di[d]; 047 nj = u.j + dj[d]; 048 if ( D[ni][nj] == INFTY && 049 (G[ni][nj] == EMPTY || G[ni][nj] == THREE)){ 050 D[ni][nj] = D[u.i][u.j] + 1; 051 Q.push(Point(ni, nj)); 052 } 053 } 054 } 055 056 return INFTY; 057 } 058 059 int manhattanDist( int i , int j ){ 060 return max(i, two[1].i)-min(i, two[1].i) + 061 max(j, two[1].j)-min(j, two[1].j); 062 } 063 064 int getWidth( int i, int j, int d){ 065 int w = 0; 066 while(1){ 067 if ( G[i][j] == TWO ) return w; 068 if ( G[i][j] != EMPTY ) return -1; 069 i += di[d]; j += dj[d]; w++; 070 } 071 } 072 073 bool isSeq( int i, int j, int d, int w, char ch ){ 074 for ( int s = 0; s < w; s++, i += di[d], j += dj[d] ){ 075 if ( G[i][j] != ch ) return false; 076 } 077 return true; 078 } 079 080 bool cut(int i, int j){ 081 for ( int d = 0; d < 4; d++ ){ 082 int w = getWidth(i+di[d], j+dj[d], d); 083 if ( w <= 0 ) continue; 084 if ( w == 1 || w == 2 ){ 085 if ( isSeq( i+di[(d+1)%4], j+dj[(d+1)%4], d, w+2, TWO ) || 086 isSeq( i+di[(d+3)%4], j+dj[(d+3)%4], d, w+2, TWO ) ) return true; 087 } else { 088 if ( isSeq( i+di[(d+1)%4], j+dj[(d+1)%4], d, w+2, TWO ) && 089 isSeq( i+di[(d+3)%4]*2, j+dj[(d+3)%4]*2, d, w, EMPTY ) || 090 isSeq( i+di[(d+3)%4], j+dj[(d+3)%4], d, w+2, TWO ) && 091 isSeq( i+di[(d+1)%4]*2, j+dj[(d+1)%4]*2, d, w, EMPTY ) ) { 092 return true; 093 } 094 } 095 } 096 097 return false; 098 } 099 100 101 void dfs( int i, int j, int dist, int pre ){ 102 if ( i == two[1].i && j == two[1].j ){ 103 mincost = min( mincost, dist + bfs() ); 104 return; 105 } 106 107 if ( dist + manhattanDist(i, j) > mincost ) return; 108 109 if ( pre != -1 ){ 110 for ( int r = 0; r < 4; r++ ){ 111 if ( r == pre ) continue; 112 if ( i+di[r] == two[1].i && j+dj[r] == two[1].j ) continue; 113 if ( G[i+di[r]][j+dj[r]] == TWO ) return; 114 } 115 } 116 117 G[i][j] = TWO; 118 119 if ( cut(i, j) ) return; 120 121 int ni, nj; 122 for ( int d = 0; d < 4; d++ ){ 123 ni = i + di[d]; 124 nj = j + dj[d]; 125 char target = G[ni][nj]; 126 if ( target == EMPTY || (ni == two[1].i && nj == two[1].j ) ){ 127 dfs( ni, nj, dist + 1, (d+2)%4 ); 128 G[ni][nj] = target; 129 } 130 } 131 } 132 133 void compute(){ 134 mincost = INFTY; 135 dfs( two[0].i, two[0].j, 0, -1 ); 136 if ( mincost >= INFTY ) cout << 0 << endl; 137 else cout << mincost << endl; 138 } 139 140 bool input(){ 141 cin >> N >> M; 142 if ( N == 0 && M == 0 ) return false; 143 for ( int i = 0; i < N+2; i++ ) G[i][0] = G[i][M+1] = OBSTACLE; 144 for ( int j = 0; j < M+2; j++ ) G[0][j] = G[N+1][j] = OBSTACLE; 145 146 int s2c, s3c; 147 s2c = s3c = 0; 148 for ( int i = 1; i <= N; i++ ){ 149 for ( int j = 1; j <= M; j++ ){ 150 cin >> G[i][j]; 151 if ( G[i][j] == TWO ) two[s2c++] = Point(i, j); 152 if ( G[i][j] == THREE ) three[s3c++] = Point(i, j); 153 } 154 } 155 return true; 156 } 157 158 main(){ 159 while( input() ) compute(); 160 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |