パソコン甲子園 2003 問題 030
2006.07.06 12:44 パソコン甲子園
[問題]
図のようなマス目の「紙」があり、(1, 2)のように x, y の値の対でその上の位置を示すことにします。値は 0 から始まる整数とします。
この「紙」にインキを滴下します。インキ滴には「大」「中」「小」の3サイズがあり、インキ滴の落ちた地点を中心に図のように周囲も色がつきます。図で☆が中心、○が色の滲む範囲です。

「紙」は、最初は「まっしろ」つまり、どのマスも色の濃さを示す値が 0 とします。インキ滴が落ちるごとに値が 1 ずつ増えていきます。「小の滴」が (1, 2)、「中の滴」が (3, 2) に落ちた場合、各マスの値は次図の左部のようになります。なお空白は値 0 を示します。滲む範囲が紙の外にもなる場合は、紙の外部を無視して下さい。
例えば、白紙に、「小の滴」を (8, 0) に落とした場合は、次図の右部のように y = -1 に相当する部分を無視することになります。同じ場所に複数のインキ滴が落ちることもありえます。

落とすインキ滴」の x, y, サイズ(小 = 1, 中 = 2, 大 = 3)を入力として読み込んで、色のついてない部分(まだ滲んでこない部分)のマス目の個数と、一番濃いマス目の濃さを出力するプログラムを作成して下さい。なお、「紙」の大きさを 10 × 10 とします。滴下される点の位置を (x, y) とすると、( 0 ≦ x < 10 ), ( 0 ≦ y < 10 ) です。
[入力]
x1,y1,size x2,y2,size . . .
[出力]
色のついていない部分のマス目の個数を第1行目に。1番濃いマス目の濃さを第2行目に出力して下さい。
[入力例]
2,5,3 3,6,1 3,4,2 4,5,2 3,6,3 2,4,1
[出力例]
77 5
[解説]
この類の問題を解くためのプログラムでは、原点(インキを落とす座標)からの相対座標を求めるために、if 文をごちゃごちゃに駆使し、プログラムが汚くなってしまうケースがよく見うけられます。ポイントは以下の2点です。
- 紙からインキがはみ出るか否かを調べることを避けるために、いわゆる"番兵"として、紙を表す2次元配列のサイズを x 軸, y 軸それぞれについて 4 づつ増やします(下図参照)。ここで、インキを落とす範囲は、2 ≦ x ≦ 11、 2 ≦ y ≦ 11 となります。番兵の領域に滲んだインキがはみ出ても、配列のサイズを超えることはありません。
- インキが落とされた原点 (x, y) からの相対座標を求めるために、(x, y) からの差分を記録した配列 dx[], dy[] を用意します(下図参照)。左図は x, y 座標の差分を表します。配列のインデックスの順番を、右図のようにしておくと便利です(プログラム例参照)。


// @author yutaka C++ #include<stdio.h> #define MAX 10 using namespace std; int paper[MAX + 4][MAX + 4]; // +4 = 番兵 void initialize(){ for ( int y = 0; y < MAX + 4; y++ ){ for ( int x = 0; x < MAX + 4; x++ ) paper[y][x] = 0; } } void drop( int x, int y, int size ){ x += 2; y += 2; // 番兵の分を足す static const int dx[13] = {0, 1, 0, -1, 0, 1, -1, -1, 1, 2, 0, -2, 0}; static const int dy[13] = {0, 0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2}; int limit = size * 4 + 1; for ( int r = 0; r < limit; r++ ) paper[y + dy[r]][x + dx[r]]++; } main(){ int x, y, size; int numberOfEmpty = 0; int maxValue = 0; initialize(); while ( scanf("%d,%d,%d", &x, &y, &size) != EOF ){ drop( x, y, size ); } for ( int y = 2; y <= 11; y++ ){ for ( int x = 2; x <= 11; x++ ){ if ( paper[y][x] == 0 ) numberOfEmpty++; if ( paper[y][x] > maxValue ) maxValue = paper[y][x]; } } printf("%d\n%d\n", numberOfEmpty, maxValue); }
| コメント(0) | トラックバック(0) | ↑ページトップ |