Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-26

Gems

| 19:52

ボード中の2つの隣接する宝石を入れ替えた時に、3つ以上宝石が並ぶかどうか。自力で解けると思って実装したが、重複して数えてしまってうまくいかず、結局Editorialを見た。

class Gems {
public:
    int numMoves(vector <string> board) {
        int moves = 0;
        const static int d[DIR_KINDS][2] = {
            { 0, 1}, { 1, 0}, { 0,-1}, {-1, 0} };
        const int h=board.size(), w=board[0].length();
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                const char gem = board[y][x];
                for (int i = 0; i < DIR_KINDS/2; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (!isInRage(dy,dx,h,w)) continue;
                    if (gem == board[dy][dx]) continue;
                    if (isAligned(gem,dy,dx,i,board,h,w) ||
                      isAligned(board[dy][dx],y,x,i+DIR_KINDS/2,board,h,w)) {
                        moves++;
                    }
                }
            }
        }
        return moves;
    }
private:
    const static int DIR_KINDS = 4;
    bool isInRage(const int y, const int x, const int h, const int w) {
        return 0<=y&&y<h && 0<=x&&x<w;
    }
    bool isAligned(const char gem, const int dy, const int dx, const int dir,
              const vector<string>& board, const int h, const int w) {
        const static int CHECK_KINDS = 4;
        const static int check[DIR_KINDS][CHECK_KINDS][2][2] = {
            { {{-1, 0},{ 1, 0}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}} },
            { {{-1, 0},{ 1, 0}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}} } };
        for (int j = 0; j < CHECK_KINDS; j++) {
            for (int k = 0; k < 2; k++) {
                const int cy = dy + check[dir][j][k][0];
                const int cx = dx + check[dir][j][k][1];
                if (!isInRage(cy,cx,h,w)) break;
                if (gem != board[cy][cx]) break;
                if (k == 2-1) return true;
            }
        }
        return false;
    }
};