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; }