fc2ブログ



ぐるぐる模様

2007.07.27 22:17  パソコン甲子園 2006


[問題] パソコン甲子園 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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ