お城の堀

パソコン甲子園2007予選問題

問題09 お城の堀

概要

２次元配列上に地面'.', 堀'#', 天守閣'&' で表されたお城の見取図が与えられ、忍者が見取図の外側から天守閣（見取図上に１つしかない）に至るまでに、堀から這い上がらなくてはならない最小回数を求めよ。忍者は堀の中および地面を東西南北４方向に動くことができる。例えば

.###.
#...#
#.&.#
#...#
.###.

の見取図では、答えは 1

#######
#.....#
#.###.#
#.#&#.#
#.###.#
#.....#
#######

の見取図では、答えは 2

######
######
##..##
##&.##
##..##
######
######

の見取図では、答えは 1
（※忍者は堀を泳ぐことができるので、2 ではない）

########################################
#......................................#
#..#########...######################..#
#..#.......#...#....................#..#
#..#.......#...#.##################.#..#
#..#.####..#...#.#..........#.#...#.#..#
#..#.#..#..#...#.#....#######.#...#.#..#
#..#.####..#...#.#....#.......#...#.#..#
#..#.......#...#.#....#.#####.#...#.#..#
#..#.......#...#.#....#.#.&.#.#...#.#..#
#..#########...#.######.#####.#####.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#....................#..#
#..............######################..#
#......................................#
#......................................#
########################################

の見取図では、答えは 4


見取図のサイズは最大 100 × 100 である。

解法

天守閣'&'の位置（ci, cj）から深さ優先探索を反復することによって解くことができます。
(ci, cj) と隣接する地面、それらに隣接する地面...を色0で塗りつぶします。
色0に隣接する堀、それらに隣接する堀...を色1で塗りつぶします。
色1に隣接する地面、それらに隣接する地面...を色2で塗りつぶします。
色2に隣接する堀、それらに隣接する堀...を色3で塗りつぶします。
.
.
.
この処理の過程で、見取図からはみ出た時点の色nの半分が解となります。

サンプルプログラム

001 #include<iostream>
002 #include<string>
003 #define MAX 100
004 using namespace std;
005 #define GROUND '.'
006 #define CASTLE '&'
007 #define MOAT '#'
008 #define INFTY (1<<21)
009 
010 int H, W;
011 char G[MAX+2][MAX+2];
012 int T[MAX+2][MAX+2];
013 pair<int, int> castle;
014 
015 bool fill( int i, int j, int color, char target ){
016     T[i][j] = color;
017     if ( i == 0 || j == 0 || i == H + 1 || j == W + 1 ) return true;
018     static const int di[4] = {0, -1, 0, 1};
019     static const int dj[4] = {1, 0, -1, 0};
020     int ni, nj;
021     for ( int r = 0; r < 4; r++ ){
022         ni = i + di[r]; nj = j + dj[r];
023         if ( (G[ni][nj] == target && T[ni][nj] == INFTY) || T[ni][nj] < color ){
024             if ( fill( ni, nj, color, target ) ) return true;
025         }
026     }
027     return false;
028 }
029 
030 int compute(){
031     int color = 0;
032     
033     for ( int i = 0; i < H + 2; i++ ){
034         for ( int j = 0; j < W + 2; j++ ) T[i][j] = INFTY;
035     }
036     
037     while(1){
038         if ( fill( castle.first, castle.second, color, GROUND ) ) return color;
039         color++;
040         if ( fill( castle.first, castle.second, color, MOAT ) ) return color;
041         color++;
042     }
043 }
044 
045 bool initialize(){
046     cin >> W >> H;
047     if ( W == 0 && H == 0 ) return false;
048     for ( int i = 0; i < H + 2; i++ ) G[i][0] = G[i][W+1] = GROUND;
049     for ( int j = 0; j < W + 2; j++ ) G[0][j] = G[H+1][j] = GROUND;
050     
051     for ( int i = 1; i <= H; i++ ){
052         for ( int j = 1; j <= W; j++ ) {
053             cin >> G[i][j];
054             if ( G[i][j] == CASTLE ) {
055                 castle = make_pair(i, j);
056                 G[i][j] = GROUND;
057             }
058         }
059     }
060     return true;
061 }
062 
063 main(){
064     while(initialize()){
065         cout << compute()/2 << endl;
066     }
067 }