There are two test cases with this problem, the first test case is shown below and the second is a hidden test case that I still can't access. The first test case works perfectly however the second test case is showing me a runtime error. I am not sure how to proceed from here.
Help Donkey find refuge in the swamp. Unfortunately for him, Shrek’s swamp is a bit of a MAZE, and we need to help him find his way to Shrek’s hut. Donkey can only move up, down, right, and left, and he can only travel on dirt and lily pads.
Input Format
The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with two integers, r and c, denoting the number of rows and columns in the maze. The following r rows will contain c characters: o – represents a Lily Pad . – represents dirt. W – represents water, Donkey cannot walk on these T – represents a tree, Donkey cannot walk on these M – represents mud, Donkey cannot walk on these D – represents Donkey’s current location, or the starting point of the maze. S – represents Shrek’s hut, or the end point of the maze.
Constraints
None.
Output Format
The output should be “We Making Waffles!!”, if it is possible for Donkey to make it to Shrek’s swamp, and “Silence is a friend that never betrays”, is it is not possible.
Sample Input 0
2
5 5
D..T.
.WoWW
.WooW
MMM.T
MMM.S
5 5
DTT..
...MM
WWMMM
WWMMM
TSMMM
Sample Output 0
We Making Waffles!!
Silence is a friend that never betrays
This is my code
import collections
for i in range(int(input())):
wall, clear, goal = 1, 0, 'S'
width,height=map(int,input().split())
def bfs(maze, start):
queue = collections.deque()
queue.append(start)
seen = set([start])
while queue:
path = queue.popleft()
x, y = path
if maze[y][x] == goal:
return True
for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
if ( 0 <= x2 < width and
0 <= y2 < height and
maze[y2][x2] != wall and
(x2, y2) not in seen):
queue.append( (x2, y2))
seen.add((x2, y2))
return False
mat=[]
for i in range(width):
mat.append(list(str(input())))
def change(lol):
for index,item in enumerate(lol):
if isinstance(item, list):
change(item)
if item=='.':
lol[index] = 0
elif item=='o':
lol[index] = 0
elif item=='W':
lol[index]= 1
elif item== 'M':
lol[index]=1
elif item== 'T':
lol[index] =1
return lol
change(mat)
def find(matrix, item):
for i in range(len(matrix)):
try:
j = matrix[i].index(item)
return (i, j)
except ValueError:
pass
start=(find(mat,'D'))
end=(find(mat,'S'))
mat[start[0]][start[1]]= 0
final=(bfs(mat,(start)))
if final== True:
print("We Making Waffles!!")
else:
print("Silence is a friend that never betrays")
Because of the hidden test case, I am not sure what caused the runtime error, especially with the first testcase running perfectly fine.
I was able to fix the runtime error! Here is my solution to help other people:
import sys
def isSafe(mat, visited, x, y):
return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and \
not (mat[x][y] == 0 or visited[x][y])
def findShortestPath(mat, visited, i, j, dest, min_dist=sys.maxsize, dist=0):
if (i, j) == dest:
return min(dist, min_dist)
visited[i][j] = 1
if isSafe(mat, visited, i + 1, j):
min_dist = findShortestPath(mat, visited, i + 1, j, dest, min_dist, dist + 1)
if isSafe(mat, visited, i, j + 1):
min_dist = findShortestPath(mat, visited, i, j + 1, dest, min_dist, dist + 1)
if isSafe(mat, visited, i - 1, j):
min_dist = findShortestPath(mat, visited, i - 1, j, dest, min_dist, dist + 1)
if isSafe(mat, visited, i, j - 1):
min_dist = findShortestPath(mat, visited, i, j - 1, dest, min_dist, dist + 1)
visited[i][j] = 0
return min_dist
def findShortestPathLength(mat, src, dest):
i, j = src
x, y = dest
if not mat or len(mat) == 0 or mat[i][j] == 0 or mat[x][y] == 0:
return -1
(M, N) = (len(mat), len(mat[0]))
visited = [[False for _ in range(N)] for _ in range(M)]
min_dist = findShortestPath(mat, visited, i, j, dest)
if min_dist != sys.maxsize:
return min_dist
else:
return -1
def change(lol):
for index,item in enumerate(lol):
if isinstance(item, list):
change(item)
if item=='.':
lol[index] = 1
elif item=='o':
lol[index] = 1
elif item=='W':
lol[index]= 0
elif item== 'M':
lol[index]=0
elif item== 'T':
lol[index] =0
return lol
def find(matrix, item):
for i in range(len(matrix)):
try:
j = matrix[i].index(item)
return (i, j)
except ValueError:
pass
if __name__ == '__main__':
for i in range(int(input())):
nums= input().split()
nums= list(map(int,nums))
mat=[]
for i in range(nums[0]):
mat.append(list(str(input())))
change(mat)
src=(find(mat,'D'))
dest=(find(mat,'S'))
mat[src[0]][src[1]]= 1
mat[dest[0]][dest[1]]=1
min_dist = findShortestPathLength(mat, src, dest)
if min_dist != -1:
print("We Making Waffles!!")
else:
print("Silence is a friend that never betrays")")