AOJ 1193: Chain Disappearance Puzzle

問題

Chain Disappearance Puzzle | Aizu Online Judge

横方向のみ考えるぷよぷよっぽいゲームの得点を求めよ

方針

• 与えられた盤面で横方向に3つ以上並んでるやつを全て-1に書き換える
• 各列ごとに-1を詰める
• -1に書き換えられる部分がなくなったら終了して得点を表示する

コード

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define rep(i,n) for(int i=0; i<(n); ++i)

int stones[11][5];
int main(void){
    int H;
    while(cin >> H && H) {
        rep(i, H) rep(j, 5) cin >> stones[H-i-1][j];
        bool isFinished = false;
        int score = 0;
        while(!isFinished) {
            isFinished = true;
            rep(i, H) {
                rep(j, 3) {
                    if(stones[i][j]!=-1 &&
                       stones[i][j]==stones[i][j+1] &&
                       stones[i][j]==stones[i][j+2]) {
                        isFinished = false;
                        int d = stones[i][j];
                        for(; stones[i][j]==d && j<5; ++j) {
                            stones[i][j] = -1;
                            score += d;
                        }
                    }
                }
            }
            rep(column, 5) {
                for(int row=1; row<H; ++row) {
                    if(stones[row-1][column]==-1 && stones[row][column]!=-1) {
                        for(int i=row; i>0&&stones[i-1][column]==-1; --i) {
                            swap(stones[i-1][column], stones[i][column]);
                        }
                    }
                }
            }
        }
        cout << score << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1895866

反省

サンプル入力に対しては正解するのにsubmitしたらWAが出てしまい、なんでだろうと思っていたら

9 1 2 3 4
1 2 9 9 9

みたいな入力に対して

- 1 2 3 4
1 2 - - -

みたいな消し方をしているバグがあった。

これはarray[y][w]がarray[y+1][0]と同じになる性質に由来するもので、境界チェックを怠っていたのが原因。

for(; stones[i][j]==d && j<5; ++j) {のj<5を入れ忘れていたことに気がついて修正したらAC。

C/C++の配列（のように見えるもの）はarray[10]を*(array+10)という意味にするシンタックスシュガーでしかない。 だから10[array]みたいに書いても動くし、二次元配列も足し算の結果が同じなら同じところにアクセスしてしまう。（こんな感じ）

境界チェックの重要性！