AOJ 0207 Block

方針

自分で処理しやすいようにマップ作っていって,始点の位置にある色と同じ色を始点と接している場所から塗りつぶしていく.

コード

typedef pair<int, int> P;

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int w, h, xs, ys, xg, yg, n;

int m[128][128];
int f[128][128];

int main()
{
    int c, d, x, y, s;
    bool found;

    while(cin >> w >> h, w|h)
    {
        cin >> xs >> ys >> xg >> yg >> n;
        xs--, ys--, xg--, yg--;

        memset(m, 0, sizeof m);
        memset(f, 0, sizeof f);

        for(int i = 0; i < n; i++)
        {
            cin >> c >> d >> x >> y;
            x--, y--;

            for(int j = 0; j < 4; j++)
                for(int k = 0; k < 2; k++)
                    m[y + (d ? j : k)][x + (d ? k : j)] = c;
        }

        s = m[ys][xs];
        found = false;

        queue<P> que;
        for(que.push(make_pair(ys, xs)); !que.empty(); que.pop())
        {
            P p = que.front();
            f[p.first][p.second] = 1;

            if(p.first == yg && p.second == xg)
            {
                found = true;
                break;
            }

            for(int i = 0; i < 4; i++)
            {
                int py = p.first + dy[i], px = p.second + dx[i];

                if(0 <= py && 0 <= px && py < h && px < w && f[py][px] == 0 && m[py][px] == s)
                {
                    que.push(make_pair(py, px));
                }
            }
        }

        cout << (found ? "OK" : "NG") << endl;
    }
}

余談

関係ないことですが,明日演奏会があります.緊張します.