Manhattan Wiring

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem E

[難易度]　★★★★

[解説]

深さ優先探索　＋　枝狩り　＋　幅優先探索

まず、深さ優先探索（バックトラック）で、２と２を繋ぐパスを探します（総当り）。
パスを探す過程で、例えば以下のような「無駄な」あるいは「ありえない」部分パスを発見したら枝を刈ります。

22
22

ワイヤーが接してしまう場合

202
222

これらの回転

2002
2222

これらの回転

*000..00*
2000..002
2222..222

これらの回転

などなど、、.(ここまで刈ればＰＯＪでも受理されます)

２と２を繋ぐパスを発見したときに、３と３を繋ぐ最短パスを幅優先探索で求め、最小値を更新していきます。

[サンプルプログラム]

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 }