#!/usr/bin/python # -*- coding: utf-8 -*- # NOI '07 - Day 1, Problem 3 # Surrounding Battalions (调兵遣将) # # Solution Checker for Experimentation # By Alex Li import collections import sys def main(): if len(sys.argv) < 2: sys.exit("Usage: surround_check.py ") fi = open(sys.argv[1], "r") fi.readline() # discard test case number n, m = map(int, fi.readline().strip().split()) g = [[ ' ' ]*m for _ in xrange(n)] # the grid r = [[False]*m for _ in xrange(n)] # research centers v = [[False]*m for _ in xrange(n)] # visited for i in range(n): line = fi.readline().strip() for j in range(m): if line[j] == 'O': g[i][j] = '.' r[i][j] = True else: g[i][j] = line[j] fi.close() fo = open(sys.argv[2], "r") ans = int(fo.readline().strip()) for _ in xrange(ans): line = fo.readline().strip() if not line: sys.exit('time not match') x1, y1, x2, y2 = map(int, line.strip().split()) if abs(x1 - x2) + abs(y1 - y2) != 1: sys.exit('move error') x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1 if ((not 0 <= x1 < n) or (not 0 <= y1 < m) or (not 0 <= x2 < n) or (not 0 <= y2 < m)): sys.exit('outside') if g[x1][y1] != '#': sys.exit('move error') if g[x2][y2] == '#': sys.exit('overlap') g[x1][y1], g[x2][y2] = g[x2][y2], g[x1][y1] fo.close() queue = collections.deque() for i in xrange(n): for j in xrange(m): if r[i][j] and g[i][j] == '#': sys.exit('overlap') if (i == 0 or j == 0 or i == n - 1 or j == m - 1) and g[i][j] == '.': queue.append((i, j)) while queue: x, y = queue.popleft() if (not 0 <= x < n) or (not 0 <= y < m): continue if r[x][y]: sys.exit('not surround') if v[x][y] or g[x][y] != '.': continue v[x][y] = True queue.append((x - 1, y)) queue.append((x + 1, y)) queue.append((x, y - 1)) queue.append((x, y + 1)) print 'yes' if __name__ == '__main__': main()