Given a N * N maze, and string of N,E,W,S denoting positions to move to. I need to determine how many moves are possible in sequence out of a string (containing these 4 letters only) from each cell as starting point.
The maze cells are denoted by 0,1 ,where 0 denotes an obstacle and 1 denotes free path to move on.
For eg- If string is NNN , and maze is
0101
1001
0000
1111
now for all cell in first row we cant go N(i..e up) so the answer is 0 for (0,0),(0,1),(0,2),(0,3).
For(1,0) it is blocked so the answer is 0 again.
For(1,1),(1,2),(2,0),(2,3) I can go only 1 N of NNN so the answer is 1 for them.
For (2,1)I can traverse 2 characters of string so the answer is 2.
For(2,2)I can traverse 3 characters so the answer is 3.
For last row, it is blocked so the answer is 0 since we can't move.
I used recursion to check for valid moves and calculated for each step.
int fun(maze[][], i) // here x and y denotes position which are intialized when code runs for each cell in maze
{
if(x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == '1') // valid conditions
{
while(i<l)
{
if(s[i]=='N')
x--;
// and so on defining the moves depending on current string character
if(fun(maze,i++)==1) // moving 1 step forward in string
{
possible++ //increment counter
}
return 1;
}
}
else
return 0;
}
Is there a way to do this more optimally ? How can I reduce its time complexity ?