EMPTY=0
BLACK=1
WHITE=-1


class Go:
	## Initializes self.board to a list[r][c]=EMPTY.
	def __init__(self,boardSize=19):
		self.boardSize=boardSize
		self.board=[[EMPTY]*boardSize for x in range(boardSize)]
		self._temp=[[EMPTY]*boardSize for x in range(boardSize)]

	## Executes a move.
	#
	#  Doesn't check for kos. Suicide not allowed.
	#
	#  @param color BLACK or WHITE
	#  @return True on success, False on failure (illegal move)
	def move(self,color,row,col):
		if self.board[row][col]!=EMPTY: return False

		self.board[row][col]=color

		# capture neighbors
		for r,c in ((-1,0),(1,0),(0,-1),(0,1)):
			self._clearTemp()
			if not self._floodFill(-color,row+r,col+c): self._remove()

		# check for suicide
		self._clearTemp()
		if not self._floodFill(color,row,col):
			self.board[row][col]=EMPTY
			return False
		return True

	## Checks for liberties of a stone at given coordinates.
	#
	#  The stone's group is marked with True in self.temp, ready for capture if needed. Recursively called for stone's neighbors.
	#
	#  @return True if alive, False if captured
	def _floodFill(self,color,row,col):
		if col<0 or col>=self.boardSize or row<0 or row>=self.boardSize: return False # out of range
		if self._temp[row][col]: return False # already visited
		if self.board[row][col]==EMPTY: return True # found a liberty
		if self.board[row][col]!=color: return False # opponent's stone
		self._temp[row][col]=True # set visited
		return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors

	## Removes stones at coordinates marked with True in self.temp.
	def _remove(self):
		for r in range(self.boardSize):
			for c in range(self.boardSize):
				if self._temp[r][c]: self.board[r][c]=EMPTY

	def _clearTemp(self):
		for i in range(self.boardSize):
			for j in range(self.boardSize):
				self._temp[i][j]=EMPTY

def exportBoard(board):
	substitutions={EMPTY:".", BLACK:"X", WHITE:"O"}
	return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board)


def isLegalPosition(board):
	boardSize=len(board)
	temp=[[None]*boardSize for x in range(boardSize)]

	for r in range(boardSize):
		for c in range(boardSize):
			if board[r][c]==EMPTY: continue
			if temp[r][c]: continue
			if not dfs([(r,c)],board,temp): return False
	return True


def dfs(stack,board,mask):
	boardSize=len(board)
	(r,c)=stack[0]
	color=board[r][c]

	while len(stack)>0:
		(r,c)=stack.pop()
		if board[r][c]==EMPTY: return True
		elif board[r][c]!=color: continue
		elif mask[r][c]: return True
		mask[r][c]=True
		for (x,y) in ((0,-1),(-1,0),(0,1),(1,0)):
			if 0<=r+y<boardSize and 0<=c+x<boardSize:
				stack.append((r+y,c+x))
	return False