C中可能的路径数

Question

所以，我正在尝试解决这个问题，我有一个矩形字段，我可以通过6种方式移动：

• 向上
• 对
• 对角线（右/上）
• 左（成本1）
• 向下（成本1）
• 2 Right和1 Up，我把它叫做象棋（费用2）

如果代码达到或超过10，代价将停止代码。

这是我的代码：

#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;
}

我认为它会达成一个解决方案，但它需要花费太多时间，即使对于小型领域......我如何改进我的代码？我应该采取另一种方法解决这个问题吗？

Answer 1

我看到两种相当简单的方法来改进你的代码。

更改：

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

至

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

由于您只能以1的成本左右移动，因此可以将其添加到成本检查中以稍早结束递归。就像是：

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