パソコン甲子園 2003 問題 030

[問題]
図のようなマス目の「紙」があり、(1, 2)のように x, y の値の対でその上の位置を示すことにします。値は 0 から始まる整数とします。

この「紙」にインキを滴下します。インキ滴には「大」「中」「小」の３サイズがあり、インキ滴の落ちた地点を中心に図のように周囲も色がつきます。図で☆が中心、○が色の滲む範囲です。

「紙」は、最初は「まっしろ」つまり、どのマスも色の濃さを示す値が 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
   .
   .
   .

[出力]
色のついていない部分のマス目の個数を第１行目に。１番濃いマス目の濃さを第２行目に出力して下さい。

[入力例]

2,5,3
3,6,1
3,4,2
4,5,2
3,6,3
2,4,1

[出力例]

77
5

[解説]
この類の問題を解くためのプログラムでは、原点（インキを落とす座標）からの相対座標を求めるために、if 文をごちゃごちゃに駆使し、プログラムが汚くなってしまうケースがよく見うけられます。ポイントは以下の２点です。

• 紙からインキがはみ出るか否かを調べることを避けるために、いわゆる"番兵"として、紙を表す２次元配列のサイズを 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);
}