0 points Consider an n × n grid (indexed n-1). Say we want to draw a path from t

Question

0 points Consider an n × n grid (indexed n-1). Say we want to draw a path from the lower left grid point (0,0) to the upper right grid point, (n -1,n 1) by travelling only east or north cell-by-cell (no back-tracking is allowed, so we cannot travel west or south). We are interested in how many different paths are there in terms of n. For example, for n = 4, the number of paths from (0,0) to (33) is 20 (see Figure 1). (a) At a particular grid point (i.j), how many ways are there of reaching this point in terms of adjacent grid points? b) How many paths are there from (0.0) to (n-1,n1 for n-5? Page 2 (0,3) 1 (1,3) 4 2,3) 10 3,3) 20 (0,2) 1 1,2) 3 (2,2) 6 3,2) 10 (0,0) 1 1,0 (2,0) 1 3,0) 1 Figure 1: Grid Example for n 4 (c) How many paths are there from (0,0) to (n-1,n-1) for n-10? d) Give a general formula in terms of n for the number of paths.

Explanation / Answer

# Hey i provide complete working code written in python3 only u need to copy this code and paste in ur text editor u must have to worry about indent... indent error will not be accepts if u write in comment box.

# Code follows DYNAMIC sol and also use memorization technique so u got too much of code already

# i hope u will UPVOTE me...

global c
c=0
global calcPath
calcPath=[[0 for i in range(4)] for j in range(4)]

def Path(matrix,row,col,p,q):
   global c
   c+=1
   if (row > p) or (col > q) or matrix[row][col]==0:
       return 0
   if row==p and col==q:
       return 1
   return (Path(matrix,row,col+1,p,q)+Path(matrix,row+1,col,p,q))

#Finding all paths from source to destination in marix with going left and down only
#Dynamic programming memorizing a paths in matrix so do not calculate redudant
def Path_Memorize(matrix,row,col,p,q):
   global c
   c+=1
   if (row > p) or (col > q) or matrix[row][col]==0:
       return 0
   if row==p and col==q:
       return 1
   if calcPath[row][col]==0:
       calcPath[row][col]=(Path_Memorize(matrix,row+1,col,p,q)+Path_Memorize(matrix,row,col+1,p,q))
       return calcPath[row][col]
   else:
       return calcPath[row][col]

matrix=[[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]
#num=Path(matrix,0,0,3,3)
#print(num,c)
num=Path_Memorize(matrix,0,0,3,3)
print("total combinations=",num,"Loop traverse times=",c)

#Thank You

Related Questions

Navigate

• Browse (All)
• Browse
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.