926 - Walking Around Wisely

Difficulty : medium

Solution Description :

DP problem

Set the disconnect road (You can use 4 dimensional Boolean array isConnect[][][][])
Initially set true to all value of isConnect array.
1. If input: Px Py S 
then set isConnect[Px][Py][Px][Py-1] = isConnect[Px][Py-1][Px][Py] = false
2. If input: Px Py W 
then set isConnect[Px][Py][Px-1][Py] = isConnect[Px-1][Py][Px][Py] = false
3. If input: Px Py N
then set isConnect[Px][Py][Px][Py+1] = isConnect[Px][Py+1][Px][Py] = false
4. If input: Px Py E 
then set isConnect[Px][Py][Px+1][Py] = isConnect[Px+1][Py][Px][Py] = false

Now find the ans using DP
Initially set number_of_ways[Sx][Sy]=1
number_of_ways[i][j] = number_of_ways[i-1][j] + number_of_ways[i][j-1] (Here, range of i[Sx,Ex] and j[Sy,Ey])
Remember check the disconnect road using isConnect[][][][] array.