Question

def snake (grid, row, co1): Implement a function to calculate the longest "snake" of ones that can be made from a starting position in a grid. A snake is made by moving right and down from a starting position as far as possible. o Assumption: grid will be at least 1x1, row and col will each be valid indexes in grid o Restrictions: You may not use the max() or min) functions. o Examples: (cells is a 2D list below) 0 0 0 snake (cells,e,0) snake (cells,e,2) ' snake (cells,1,1) # can't move in either direction # can go down one, then no more moves # all the way down, and then right 2 5

Answer 1

Explanation: Using dfs to compute the longest snake length. We can also do this problem by using dynamic programming but as per the restriction we can't use max(). So I used dfs instead of dp.

Source Code:

def isSafe(grid, x, y, isVisited):

if (x < len(grid)) and (y < len(grid[0])) and (grid[x][y] == 1) and (isVisited[x][y] == False):

return True

else:

return False

def dfs(grid, row, col, isVisited):

if grid[row][col] == 0:

return 0

isVisited[row][col] = True

if isSafe(grid, row+1, col, isVisited):

return dfs(grid, row+1, col, isVisited)+1

if isSafe(grid, row, col+1, isVisited):

return dfs(grid, row, col+1, isVisited)+1

return 1

def snake(grid, row, col):

numRows = len(grid)

numCols = len(grid[0])

isVisited = [[False]*numCols for i in range(numRows)]

ans = dfs(grid, row, col, isVisited)

print(ans)

cells = [[1,0,1,0],[0,1,1,0],[1,1,0,1],[0,1,1,1]]

print(cells)

snake(cells, 0, 0)

snake(cells, 0, 2)

snake(cells, 1, 1)

Output:

[[1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 0, 1], [0, 1, 1, 1]]
1
2
5

Image for clarity:

def isSafe(grid, x, y, isVisited): if (x 〈 len (grid)) and (y 〈 len(grid[0])) and (grid[x][y]-1) and (îsVisited [x][y] False): return True eise return False def dfs(grid, row, col, isVisited): if grid[row][col]-0: return 0 isVisited [row] [col] True if İsSafe(grid, row+1, col, isvi sited): return dfs(grid, row+1, col, isVisited)+1 col+1, return dfs(grid, row, col+1, isVisited)+1 İsSafe(grid, İsVi sited): if row, return 1 def snake(grid, row, col): numRows len(grid) numCols len(grid[e]) isVisited [[False] numCols for i in range(numRows)] ans dfs(grid, row, col, isVisited) print (ans) cells [[1,0,1,0], [e,1,1,0], [1,1,0,1], [0,1,1,1]] print (cells) snake (cells, 6, 0) snake (cells, 0, 2) snake (cells, 1, 1)