Rat in a maze problem

#1

how to calculate all the numbers of paths in this problem

#2

Just maintain a global counter. Increment the counter by 1 in the base case. And return false in the base case.