fc2ブログ



パソコン甲子園 2003 問題 030

2006.07.06 12:44  パソコン甲子園

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

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

ink1.gif

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

例えば、白紙に、「小の滴」を (8, 0) に落とした場合は、次図の右部のように y = -1 に相当する部分を無視することになります。同じ場所に複数のインキ滴が落ちることもありえます。

ink2.gif

落とすインキ滴」の 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 となります。番兵の領域に滲んだインキがはみ出ても、配列のサイズを超えることはありません。

  • ink3.gif
  • インキが落とされた原点 (x, y) からの相対座標を求めるために、(x, y) からの差分を記録した配列 dx[], dy[] を用意します(下図参照)。左図は x, y 座標の差分を表します。配列のインデックスの順番を、右図のようにしておくと便利です(プログラム例参照)。

  • ink4.gif

[プログラム例]

// @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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

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

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

↑ページトップ