codeiq 1021

1021.py

#coding: utf-8
import sys

def isMakePair(room):
	global h
	global w
	global cand_point

	# [1]各人のペア候補人数をセット
	while True:
		end_flg = True
		for y in range(h):
			for x in range(w):
				if room[y][x]!=-1:
					candidates = 0
					one_x = 0
					one_y = 0
					for p in cand_point:
						px = x + p[0]
						py = y + p[1]
						if px>=0 and py>=0 and px<w and py<h:
							if room[py][px]!=-1:
								candidates += 1
								one_x = px
								one_y = py
					if candidates == 1:
						# ペア候補が一人しかいない場合は両者に-1をセット
						room[y][x] = -1
						room[one_y][one_x] = -1
					else:
						# 元の値と異なる場合に候補者数をセット
						if room[y][x] != candidates:
							room[y][x] = candidates

							# 変化あり
							end_flg=False
		if end_flg==True:
			# 変化が無くなったので終了
			break

	# [2]ペアが組めない人がいるかのチェック
	zero_flg = False
	for y in range(h):
		for x in range(w):
			if room[y][x]==0:
				zero_flg=True
				break
		if zero_flg == True:
			break

	if zero_flg==True:
		# 余る人がいる
		return False
	else:
		# [3]すべてペアが組めているかのチェック
		pair_flg = True
		for y in range(h):
			for x in range(w):
				if room[y][x]!=-1:
					pair_flg=False
					break
			if pair_flg == False:
				break

		if pair_flg==True:
			# すべてペアが組めた
			return True
		else:
			# [4]候補が2人のペアを仮にペアとして、再帰
			ret = False
			for y in range(h):
				for x in range(w):
					if room[y][x]==2:
						for p in cand_point:
							px = x + p[0]
							py = y + p[1]
							if px>=0 and py>=0 and px<w and py<h:
								if room[py][px]!=-1:
									keep_p = room[py][px]

									# ペア作成（-1をセット）
									room[y][x] = -1
									room[py][px] = -1

									# 再帰呼び出し
									ret = isMakePair(room)
									if ret ==True:
										# ペアが組めたら終了
										break

									# 元に戻す
									room[y][x] = 2
									room[py][px] = keep_p
					if ret ==True:
						break
				if ret ==True:
					break
			return ret

# 標準入力より全行読み込み
lines = list(map(str, sys.stdin.read().splitlines()))

# 幅
w = len(lines[0])

# 高さ
h = len(lines)

# 人数
count = w * h

# 教室の状態テーブル
room = [[0] * w for i in range(h)]

# 欠席の箇所を-1に
for y in range(h):
	for x in range(w):
		if lines[y][x]=="X":
			count -= 1
			room[y][x] = -1

# ペア候補の座標差分
cand_point = [[1,0],[0,1],[-1,0],[0,-1]]

if count % 2 == 0:
	# 人数が偶数の場合
	if count == 0:
		# 一人もいない場合
		print ("no")
	else:
		if isMakePair(room)==True:
			# ペアが組めた
			print ("yes")
		else:
			# ペアが組めない
			print ("no")
else:
	# 奇数の人数の場合はどのような場合でもかならず一人あまる
	print ("no")