BoardProblem{Matrix}

#Problem to find the total no. of paths from initial[0][0] to final[rows-1][cols-1].Inputs are hardcoded
rows=4
cols=4
board=[[0 for i in range(cols)] for j in range(rows)]
board[1][1]=-1#Denoting the obstacles
board[2][3]=-1
board[3][0]=-1
for i in board:
	print(i)
memo=[[0 for i in range(cols)] for j in range(rows)]
count=0
#print(board)
'''
def recboard(x,y):#recursive approach when we just need to find the total no. of paths
	global count
	if x==rows-1 and y==cols-1:
		#print("Destination reached")
		count+=1
		return 
	elif x==rows or y==cols:
		return 
	else:
		#print(x,y)
		return (recboard(x,y+1),recboard(x+1,y))
recboard(0,0)
print("The no. of possible paths are: "+str(count))
'''
for i in range(1,cols):#Dynamic programming approach to find the no.of paths when there are obstacles in the board
	if board[0][i]==0:#to avoid initialization errors
		memo[0][i]=1
	else:
		memo[0][i]=0
for j in range(1,rows):
	if board[j][0]==0:
		memo[j][0]=1
	else:
		memo[j][0]=0
for x in range(1,rows):
	for y in range(1,cols):
		if board[x][y]==-1:
			memo[x][y]=0
			continue
		memo[x][y]=memo[x][y-1]+memo[x-1][y]
print("The no. of possible paths are: "+str(memo[rows-1][cols-1]))