お城の堀
2007.09.29 18:23 パソコン甲子園 2007
問題09 お城の堀
概要
2次元配列上に地面'.', 堀'#', 天守閣'&' で表されたお城の見取図が与えられ、忍者が見取図の外側から天守閣(見取図上に1つしかない)に至るまでに、堀から這い上がらなくてはならない最小回数を求めよ。忍者は堀の中および地面を東西南北4方向に動くことができる。例えば
.###. #...# #.&.# #...# .###.
の見取図では、答えは 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 }
| コメント(0) | トラックバック(0) | ↑ページトップ |