2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 11 '17 at 22:46
  • $\begingroup$ @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. $\endgroup$ – sammy Apr 12 '17 at 3:03
  • $\begingroup$ Have you tried dynamic programming? See cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Apr 12 '17 at 4:29
  • $\begingroup$ @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 ? $\endgroup$ – sammy Apr 12 '17 at 6:03
  • $\begingroup$ I dont feel you can optimize this. Its just a normal dfs algorithm. $\endgroup$ – asddf Apr 13 '17 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.