# Arup Guha
# Example of a floodfill on a 2D grid (text only)
# 6/22/2017
# Possible movements in the grid.
DX = [-1,0,0,1]
DY = [0,-1,1,0]
def main():
# Open the file and get number of cases.
myfile = open('bunnies.in', 'r')
numCases = int(myfile.readline().strip())
# Process each case.
for loop in range(numCases):
# Get grid size.
items = myfile.readline().split()
numRows = int(items[0])
numCols = int(items[1])
# Store the grid as a list of strings.
grid = []
for i in range(numRows):
grid.append(myfile.readline().strip())
start = getPos(grid, 'P')
# This is annoying...just want a grid full of False's.
used = []
for i in range(numRows):
tmp = []
for j in range(numCols):
tmp.append(False)
used.append(tmp)
# Run our floodfill from Peter.
floodfill(grid, start, used)
# See if we got to cotton tail and print accordingly.
end = getPos(grid, 'C')
if used[end[0]][end[1]]:
print("yes")
else:
print("no")
myfile.close()
def getPos(grid, ch):
# Go through each square.
for i in range(len(grid)):
for j in range(len(grid[0])):
# We found it.
if grid[i][j] == ch:
return (i, j)
def floodfill(grid,start,used):
# Mark this spot as used.
used[start[0]][start[1]] = True
# Try going in all 4 directions.
for i in range(len(DX)):
# Where we'd jump our current location in this direction.
nextX = start[0] + DX[i]
nextY = start[1] + DY[i]
# We recurse if the square exists and we've never visited it before,
# and it's a valid square to go to.
if inbounds(nextX, nextY, grid) and not used[nextX][nextY] and grid[nextX][nextY] != '#':
floodfill(grid, (nextX, nextY), used)
# Returns true iff (x,y) is a valid index into grid.
def inbounds(x,y,grid):
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])
# Get it started.
main()