AOJ 0207 - Block
書道をしないといけないのに何やってるんだろう.
#include <iostream> #include <queue> #include <cstring> const int MAX_W = 100, MAX_H = 100; typedef std::pair<int,int> P; int map[MAX_H + 1][MAX_W + 1], w, h; int bfs(P sp, P gp, int c){ //来たことがあるかを格納 int f[MAX_H + 1][MAX_W + 1] = {{0}}; std::queue<P> q; q.push(P(sp.first, sp.second)); while(q.size()){ P p = q.front(); q.pop(); //ゴールできたら成功 if(p.first == gp.first && p.second == gp.second)return 1; int vy[4] = {-1, 1, 0, 0}, vx[4] = {0, 0, -1, 1}; for(int i=0;i<4;i++){ int nx = p.first + vx[i], ny = p.second + vy[i]; if(nx >= 0 && nx <= w && ny >= 0 && ny <= h && map[ny][nx] == c && !f[ny][nx]) q.push(P(nx,ny)), f[ny][nx] = 1; } } //最後までゴールできないなら失敗 return 0; } int main(){ P sp, gp; while(std::cin >> w >> h, w && h){ memset(map,0,sizeof(map)); std::cin >> sp.first >> sp.second; std::cin >> gp.first >> gp.second; int n; std::cin >> n; //ブロックの設置 while(n--){ int c, d, x, y; std::cin >> c >> d >> x >> y; int mx, my; if(d)//w < h my = 4, mx = 2; else//w > h mx = 4, my = 2; for(int i=y;i<y+my;i++) for(int j=x;j<x+mx;j++) map[i][j] = c; } int sc = map[sp.second][sp.first]; //bfsでゴールできるか確認 if(bfs(sp, gp, sc))std::cout << "OK" << std::endl; else std::cout << "NG" << std::endl; } }