Algorithm to find the number of paths you can take in a coordinate plane-CodePudding

You're given a square of NxN (2 <= N <= 50) dots, but some of the dots can be H (blocked), meaning that you cannot go on them. You are also given T (1 <= T <= 3), the amount of turns maximum that you are allowed to make. You start at the top left of the graph, and you have to make it to the bottom right of the graph. You can only move down or to the right. Here are three examples of possible graphs.

N = 3, T = 3
...
.H.
...

Output: 2

N = 4, T = 3
...H
.H..
....
H...

Output: 6

N = 3, T = 2
.HH
HHH
HH.

Output: 0

D means move down and R means move right. For the first one the two ways are DDRR and RRDD. For the second one, the six ways are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD. For the last one, there are no ways to make it to the bottom right.

One thing I have thought is that it might be possible to solve this with DFS but I don't know how to implement it for this problem. Any help would be utmost helpful.

I have tried this recursive method, but I'm pretty sure I'm completely going the wrong way about it.

public static void step(char[][] graph, int[] pos, int turns, int max)
{
    if(turns > max) return;
    else if(pos[0] == graph.length-1 && pos[1]==graph.length-1)
    {
        count  ;
        return;
    }
    else if(pos[0] == graph.length && graph[pos[0] 1][pos[1]] == 'H') return;
    else if(pos[1] == graph.length && graph[pos[0]][pos[1] 1] == 'H') return;
    else if(graph[pos[0] 1][pos[1]] == 'H' && graph[pos[0]][pos[1] 1] == 'H') return;
    else {
        step(graph, new int[]{pos[0] 1, pos[1]}, turns 1, max);
        step(graph, new int[]{pos[0], pos[1] 1}, turns 1, max);
    }
}

CodePudding user response：

There are a few mistakes I spotted in your function :

The conditions to check if you're out of bounds should not need to check if there is an H : out of bound means there is nothing, so pos[0] == graph.length should be enough to stop.

The condition to check if there is an H blocking the way is also wrong : to be stopped, you would need to have both an H right and below you. Which mean you would still explore some path passing through H's. What you could do is to stop if you're currently on a H : if(graph[pos[0]][pos[1]] == 'H')

The recursive calls always increment turns. Are turns the number of steps you are allowed to make, or the number of times you can change direction ? If it's the latter, you need to pass the current direction in the call, and only increment if you change direction. The original call is a little bit trickier, as you don't really have a direction for the first step.

A global observation is that you seems to mix the logical "AND" operator (&&). Maybe I'm wrong, but a quick review could help you, because the "OR" seems more logical there.

CodePudding user response：

Yes. Assuming the number of turns is the number of times you change direction, you need to keep track of the direction and only increment turns when the direction changes:

public static void step(char[][] graph, int[] pos, int turns, int max,
        char dir)
{
    if(turns > max) return;
    else if(pos[0] == graph.length-1 && pos[1]==graph.length-1)
    {
        count  ;
        return;
    }
    if(pos[0] < graph.length && pos[1] < graph.length
            && graph[pos[0]][pos[1]] != 'H') {
        step(graph, new int[]{pos[0] 1, pos[1]}, dir != 'R' ? turns : turns 1, max, 'D');
        step(graph, new int[]{pos[0], pos[1] 1}, dir != 'D' ? turns : turns 1, max, 'R');
    }
}

The initial call would pass any character that is neither 'D' nor 'R':

    step(graph, new int[]{0, 0}, 0, t, '?');