825 - Walking on the Safe Side

Difficulty : medium

Solution Description :

Graph DAG, DFS problem

The starting node (1,1). Now run DFS with start node
----pop value(x,y) from stack. if x==W && y==N then increment count variable
----find two adjacency (x+1,y) and (x,y+1) of (x,y)
----for each adjacency of (x,y) if the adjacency point is valid(i.e. between 1 & R and 1 & C) and the point is not a unsafe point then push the point to stack.
----Run this process until stack is empty

At last print count
Remember W<=100, N<=100, and the ans can be long long