ぐるぐる模様
2007.07.27 22:17 パソコン甲子園 2006
[問題] パソコン甲子園 ２００６ ぐるぐる模様
整数 n が与えられ、n × n のグリッド上にぐるぐる模様を描きなさい、という問題です。
例えば n が 1 ～ 9 までの出力はそれぞれ以下のようになります。（'.' は空白を表すことにします）
n = 1 # n = 2 ## #. n = 3 ### #.# #.# n = 4 #### #..# #..# #.## n = 5 ##### #...# #.#.# #.#.# #.### n = 6 ###### #....# #.##.# #.#..# #.#..# #.#### n = 7 ####### #.....# #.###.# #.#.#.# #.#.#.# #.#...# #.##### n = 8 ######## #......# #.####.# #.#..#.# #.#..#.# #.#.##.# #.#....# #.###### n = 9 ######### #.......# #.#####.# #.#...#.# #.#.#.#.# #.#.#.#.# #.#.###.# #.#.....# #.#######
問題の定義が曖昧な気もしますが、左下角から時計回りに'#'で埋めて下さいということです。
なにやら面倒な問題ですが、いかに楽をして解くかを考えなければなりません。
①グリッド上を探索っぽく塗りつぶす
②パタンを発見して塗りつぶす
など
がありますが、これを探索っぽく、壁にぶつかったらどうのこうのと実装すると、
ハマりやすいと思います。実際多くの学生がハマってしまいました。
パタン（数列）が発見できればプログラムは比較的簡単になります。
まず、塗りつぶしていく方向は、↑→↓←の繰り返しであるとがわかります。
次に、塗りつぶす幅を考えます。
例えば、各数字を#の幅だとすると、 n = 8 の場合は、
88866442
と表されます。これは、
↑に8、→に8、↓に8、←に6、↑に6、→に4、...塗りつぶす、という意味です。
n = 9 の場合は、
999775533
と表されます。
他のnに対しても試してみると、以下のような数列になることが分かります。
n n n (n-2) (n-2) (n-4) (n-4) . . .
そして、数列の長さが n となります。
「座標(i, j)から、d 方向 に向かって幅 w だけ塗りつぶす」
といった関数またはルーチンを、繰り返すだけです。
※ n = 2 のときの出力に注意する必要があります。
本戦で wrong answer をもらった人は、n = 2 の出力が間違っていた可能性が高いです。
以下解答例です。
001 #include<stdio.h>
002
003 int n;
004 char G[100][100]; // grid
005 static int di[4] = {-1, 0, 1, 0};
006 static int dj[4] = {0, 1, 0, -1};
007
008 int main(){
009 int dir, width, i, j, a, w;
010 scanf("%d", &n);
011
012 for ( i = 0; i < n; i++ )
013 for ( j = 0; j < n; j++ ) G[i][j] = ' ';
014
015 width = n - 1;
016 i = width; j = dir = 0;
017
018 for ( a = 1; a <= (n + n % 2); a++, dir = (dir + 1) % 4 ){
019 for ( w = 0; w <= width; w++ ) G[i+di[dir]*w][j+dj[dir]*w] = '#';
020 i += di[dir] * width;
021 j += dj[dir] * width;
022 if ( a % 2 == 1 && a >= 3 ) width -= 2;
023 }
024
025 for ( i = 0; i < n; i++ ){
026 for ( j = 0; j < n; j++ ) printf("%c", G[i][j]);
027 printf("\n");
028 }
029 }
030
031
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |