0

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

  • 向上
  • 正确的
  • 对角线（右/上）
  • 左（费用为 1）
  • 羽绒服（费用为 1）
  • 2 右 1 上，我称它为象棋中的马（成本 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;
}

我确实认为它会找到一个解决方案，但它需要太多时间，即使对于小领域也是如此......我该如何改进我的代码？我应该采取另一种方法来解决这个问题吗？

4

1 回答 1

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
于 2017-12-19T10:58:30.183 回答