# Maximum Move in a maze

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 ?

• Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – D.W. Apr 11 '17 at 22:46
• @D.W. I hope the question is clear now. And we only concern from starting index of string. We don't care about subsequences. I just want to know how many characters in string I can traverse. – sammy Apr 12 '17 at 3:03
• Have you tried dynamic programming? See cs.stackexchange.com/tags/dynamic-programming/info – D.W. Apr 12 '17 at 4:29
• @D.W. I know about it but I can't seem to apply it here. I found the recursive solution. How can I use dynamic programming here ? Can you help out ? – sammy Apr 12 '17 at 6:03
• I dont feel you can optimize this. Its just a normal dfs algorithm. – asddf Apr 13 '17 at 17:01