Number of Possible Paths in C

Question

So, I am currently trying to solve this problem where I have a rectangular field and I can move in 6 ways:

• Up
• Right
• Diagonal (Right/Up)
• Left (with cost 1)
• Down (with cost 1)
• 2 Right and 1 Up, I called it Horse like in chess (cost 2)

The cost will stop the code if it reaches or exceeds 10.

Here is my code:

#include <stdio.h>

int path_counter(int lx, int ly, //length of the field in each direction
                int x, int y, //current position
                int final_x, int final_y, //position I want to reach
                int cost) //The cost will stop the code if it starts taking too many "wrong" steps (backwards)
{
    printf("taking a new step: %d, %d \n",x,y);
    if(cost > 10) return 0; //Cost beyond threshold

    else if(x < 0 || y < 0 || x >= lx || y >= ly) return 0; //Out of Bounds

    else if(x == final_x && y == final_y) return 1; //Arrived

    //Did not arrive, but still possible:
    else return path_counter(lx, ly, //up
                        x, y+1,
                        final_x, final_y,
                        cost) +
            path_counter(lx, ly, //diagonal up/right
                         x+1, y+1,
                         final_x, final_y,
                         cost) +
            path_counter(lx, ly, //right
                         x+1, y,
                         final_x, final_y,
                         cost) +
            path_counter(lx, ly, //down
                         x, y-1,
                         final_x, final_y,
                         cost+1) +
            path_counter(lx, ly, //left
                         x-1, y,
                         final_x, final_y,
                         cost+1) +
            path_counter(lx, ly, //horse
                         x+2, y+1,
                         final_x, final_y,
                         cost+2);
}

int main() {
    //Create the field
    int lx = 2; int ly = 2;
    int ix = 0; int iy = 0;
    int fx = 1; int fy = 1;
    //Initial cost
    int cost = 0;
    printf("%d",path_counter(lx,ly,ix,iy,fx,fy,cost));
    return 0;
}

I do think it will reach a solution, but it is taking too much time, even for small fields... How Can I improve my code? Should I take another approach to this problem?

Answer 1

I see two rather simple ways to improve your code.

Change:

else if(x >= lx || y >= ly) return 0; //Out of Bounds

to

else if(x < 0 || x >= lx || y < 0 || y >= ly) return 0; //Out of Bounds

Since you can only go left and down at a cost of one, you can add that to the cost-check to end the recursion a bit earlier. Something like:

future_left_cost = (final_x < x) ? x - final_x : 0;
future_down_cost = (final_y < y) ? y - final_y : 0;

if((cost + future_left_cost + future_down_cost)  >= 10) return 0; //Cost beyond threshold