Block | Aizu Online Judge

Block | Aizu Online Judge

特に難しいことはないけど、入力ケースが多いので少しめんどくさい。

int mp[105][105];
bool visited[105][105];
int w, h;
int xs, ys;
int xg, yg;
int n;
int col;

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

void solve(int x, int y) {
    visited[x][y]=1;
    if (x==xg&&y==yg) return;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx<1 || nx > w || ny < 1 || ny > h) continue;
        if (visited[nx][ny]) continue;
        solve(nx, ny);
    }
}

int main() {
    while (1) {
        memset(mp, 0, sizeof(mp));
        memset(visited, 0, sizeof(visited));
        cin >> w >> h;
        if (w==0&&h==0) break;
        cin >> xs >> ys;
        cin >> xg >> yg;
        cin >> n;
        for (int i = 0; i < n; i++) {
            int c, d, x, y; cin >> c >> d >> x >> y;
            int jl, kl;
            if (d==0)
                jl = 4, kl = 2;
            else
                jl = 2; kl = 4;

            for (int j = 0; j < jl; j++)
                for (int k = 0; k < kl; k++)
                    mp[x+j][y+k]=c;
        }
        col = mp[xs][ys];
        if (col != mp[xg][yg] || !col){
            cout << "NG" << endl;
            continue;
        }
        for (int i = 1; i <= w; i++) {
            for (int j = 1; j <= h; j++){
                if (mp[i][j] != col){
                    visited[i][j]=1;
                }
            }
        }
        solve(xs, ys);
        if (visited[xg][yg]) {
            cout << "OK" << endl;
        } else {
            cout << "NG" << endl;
        }
    }
    return 0;
}