お城の堀
2007.09.29 18:23 パソコン甲子園 2007
パソコン甲子園2007予選問題
問題09 お城の堀
概要
２次元配列上に地面'.', 堀'#', 天守閣'&' で表されたお城の見取図が与えられ、忍者が見取図の外側から天守閣（見取図上に１つしかない）に至るまでに、堀から這い上がらなくてはならない最小回数を求めよ。忍者は堀の中および地面を東西南北４方向に動くことができる。例えば
の見取図では、答えは 1
の見取図では、答えは 2
の見取図では、答えは 1
（※忍者は堀を泳ぐことができるので、2 ではない）
の見取図では、答えは 4
見取図のサイズは最大 100 × 100 である。
解法
天守閣'&'の位置（ci, cj）から深さ優先探索を反復することによって解くことができます。
(ci, cj) と隣接する地面、それらに隣接する地面...を色0で塗りつぶします。
色0に隣接する堀、それらに隣接する堀...を色1で塗りつぶします。
色1に隣接する地面、それらに隣接する地面...を色2で塗りつぶします。
色2に隣接する堀、それらに隣接する堀...を色3で塗りつぶします。
.
.
.
この処理の過程で、見取図からはみ出た時点の色nの半分が解となります。
サンプルプログラム
問題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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |
)