CODE THANKS FESTIVAL 2014 B : E - マスゲーム

Code Thanks Festival Bに参加。
Gまではサクサク解けたけどHが解けず微妙な順位。
Dまでは簡単なのでEから記事作成。
http://code-thanks-festival-2014-b-open.contest.atcoder.jp/tasks/code_thanks_festival_14_qualb_e

問題

R*Cの二次元グリッドがある。初期状態で各セルは白に塗られている。
ここでN個のクエリが与えられる。
各クエリは長方形領域を示しており、その範囲のセルを黒く塗る。

グリッド状の２つのセルの位置が与えられる。
両者を黒い隣接セルだけを辿って到達することができるか答えよ。

解法

各クエリに対するセルの黒塗り処理は愚直に行ってもO(RCN)で間に合う。
あとはBFSで到達可能セルを辿るだけ。

int H,W,N;
int sy,sx,gy,gx;
char S[100][100];
int vis[100][100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>sy>>sx>>gy>>gx;
	sy--,sx--,gy--,gx--;
	
	cin>>N;
	while(N--) {
		cin>>y>>x>>k>>l;
		FOR(i,k) FOR(j,l) S[y-1+i][x-1+j]=1;
	}
	
	if(S[sy][sx]==0) return _P("NO\n");
	
	
	vis[sy][sx]=1;
	queue<int> Q;
	Q.push(sy*100+sx);
	while(Q.size()) {
		k=Q.front();
		int cy=k/100,cx=k%100;
		Q.pop();
		FOR(i,4) {
			int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
			int ty=cy+dy[i],tx=cx+dx[i];
			if(tx<0 || ty<0 || ty>=H || tx>=W) continue;
			if(S[ty][tx]==0 || vis[ty][tx]) continue;
			if(gy==ty && tx==gx) return _P("YES\n");
			vis[ty][tx]=1;
			Q.push(ty*100+tx);
		}
	}
	_P("NO\n");
	
}

まとめ

まだ愚直解が通じるし簡単な方かな。