Hi,
I’m trying to submit my solution to Bear and Species (SPECIES Problem - CodeChef). I’m getting runtime error (NZER) on subtask 2 and 3, and WA in subtask 1.
But I couldn’t figuring out what is/are wrong with my solution. All the unit test cases that I could of think of pass locally when I tested my code.
Would be great if some one who’s smarter than me can help spot the issues. Thank you!
Here’s the latest submission:
https://www.codechef.com/viewsolution/27566173
"""
Bear and Species
Link:
https://www.codechef.com/problems/SPECIES
"""
## -----------------------------------------------------------------------------
class Solution_1(object):
"""My Solution 1"""
def solve(self, N, grid):
# print 'grid:'
# for row in grid:
# print row
dirs = [(-1,0),(0,1),(1,0),(0,-1)] # clockwise from top
def inrange(v):
return (0 <= v) and (v < N)
visited = [[0 for _ in xrange(N)] for _ in xrange(N)]
def dfs(r, c, v):
assert visited[r][c] == 0, 'Should not visit something already visited!!!'
visited[r][c] = 1
grid[r][c] = v
neighbors = [(r+y,c+x) for (y,x) in dirs if (inrange(r+y) and inrange(c+x))]
for r2,c2 in neighbors:
if grid[r2][c2] == '?' and visited[r2][c2] == 0:
dfs(r2, c2, v)
for r in xrange(N):
for c in xrange(N):
v = grid[r][c]
if v in ('B', 'P') and visited[r][c] == 0:
dfs(r,c,v)
# Need to clear the visited dict.
# visited = [[0 for _ in xrange(N)] for _ in xrange(N)]
for r in xrange(N):
for c in xrange(N):
visited[r][c] = 0
num_dots = 0
# print 'grid:'
# for row in grid:
# print row
res = 0
for r in xrange(N):
for c in xrange(N):
if visited[r][c]:
continue
v = grid[r][c]
neighbors = [(r+y,c+x) for (y,x) in dirs if (inrange(r+y) and inrange(c+x))]
if v == '?':
Qs = 0
for r2,c2 in neighbors:
v2 = grid[r2][c2]
if v2 == 'G':
return 0
elif v2 == '?':
Qs += 1
num = 2 if Qs else 3
# print '\tassigning num={} at ({},{})'.format(num, r,c)
res = num if (res == 0) else res * num
dfs(r, c, '-')
grid[r][c] = num
elif v == 'G':
###
# If the cell is a grizzly and one of its neighbors is NOT
# empty, then there can be no coexistence.
###
for r2,c2 in neighbors:
v2 = grid[r2][c2]
if v2 != '.':
return 0
elif v in ('P', 'B'):
for r2,c2 in neighbors:
v2 = grid[r2][c2]
if v2 == 'G':
return 0
elif v2 == 'B' and v == 'P':
return 0
elif v2 == 'P' and v == 'B':
return 0
elif v == '.':
num_dots += 1
visited[r][c] = 1
# print 'grid:'
# for row in grid:
# print row
MOD = int(1e9+7)
return (res + MOD) % MOD if res else (1 if num_dots < (N*N) else 0)
## -----------------------------------------------------------------------------
Solution = Solution_1
class Driver(object):
def run(self):
T = int(raw_input().rstrip())
for t in xrange(T):
N = int(raw_input().rstrip())
grid = []
for i in xrange(N):
l = str(raw_input())
row = list(l.rstrip())
assert len(row) == N, 'Expects rows to be of length {} in {}-th test case, but got size {} in the {}-th row. Line=\"{}\"'.format(N, t, len(row), i, l)
grid.append(row)
soln = Solution()
res = soln.solve(N, grid)
print res
# print '----------------------'
def main():
driver = Driver()
driver.run()
if __name__ == '__main__':
main()