926 - Walking Around Wisely
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. |
||||||||||