c-在冰上滑行益智游戏中寻找路径

Question

[我为标题道歉，我只是指定了我在这个谜题上遇到的问题。

根据遇到的星号数量，我正在制定一种行程最小的路径查找方法。

游戏规则很简单，从A到B，但我只能在一条直线上移动，并且不能停止在那个方向上移动，直到你点击星号（或B），就好像它们在每一个零上滑动一样。

例如，照片显示了从A到B的最短路径，其中23是行驶的总距离。]1

我脑海中出现的第一个想法是制作一个邻接矩阵，最初，我在这里有我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    FILE *hehehe = fopen("input.txt","r");
    //==========================ADJACENCY MATRIX INITIALIZATION=======================================//
    int row, column, i, j;
    fscanf(hehehe,"%d",&row);
    fscanf(hehehe,"%d",&column);
    char c;
    c = fgetc(hehehe);
    int matrix[row][column];
    c = fgetc(hehehe);
    for (i = 0; i < row; i++)
    {
        for (j = 0; j < column; j++)
        {
            if (c == '*'){
                matrix[i][j] = 1;
                c = fgetc(hehehe);
            }
            else if (c == 'A')
            {
                matrix[i][j] = 2;
                c = fgetc(hehehe);
            }
            else if (c == 'B')
            {
                matrix[i][j] = 3;
                c = fgetc(hehehe);
            }
            else{
                matrix[i][j] = 0;
                c = fgetc(hehehe);
            }
            if (c == 'n'){c = fgetc(hehehe);}
        }
    }
    for (i = 0; i < row; i++)
    {
        for (j = 0; j < column; j++)
        {
            //if (matrix[i][j] == 1)  printf("*");
            //else    printf(" ");
            printf("%d ",matrix[i][j]);
        }
        printf("n");
    }

    fclose(hehehe);
}

任何关于继续在照片中的每条直线上制作边缘的想法或建议都将不胜感激。感谢您提前提供的帮助。

Answer 1

在这种情况下，我认为矩阵做得太过火了。因为你不能在滑动时移动，所以你只需要一个有向图。

在制作算法时，需要记住以下几点：

• 停止点是目标或与墙/星号相邻的任何空间
• 一个顶点应该存储两个值；方向和位置
• 对于每个星号或障碍，将相邻空间添加到顶点列表中（如果它们还不存在于图形中）。它们只需要一个方向
• 对于每个B，添加一个具有所有可能方向的顶点。（或者每个方向都有一个顶点，具体取决于这是否更容易）
• 对于每个顶点，找到存储方向上最近的顶点。在两个顶点之间绘制一条边（如果它还不存在）
• 运行适当的搜索算法。如果距离很重要，请使用Dijkstra的。如果没有，请先使用"宽度"。如果有特殊的评分规则，可以考虑A*

因为你的搜索空间似乎没有那么大，我还没有完全优化算法。这就是我提到检查顶点和边是否已经添加的原因。优化这些是可能的，如果你需要，我可以帮助你，但如果语句的成本不足以保证提前优化。因为你的搜索空间很容易简化，广度优先和Dijkstra的算法是绝对完美的；它们找到了最短的路径，并且它们的性能成本远不如将它们放在2D网格上那么高。

如果你不确定如何构建你的数据结构，下面是我的方法。

1。图结构

Direction // x and y tuple/variable, integer, or string
Point // x and y tuple/variable. Note that you can use this as direction too 
Vertex
- Point
- Map < Direction, Edge > // each direction is linked to another vertex
                          // maps in C can be made with two arrays
                          // a vertex for each direction may be easier
Edge
- Vertex // you can store both vertices, but you only need to store the one being moved to. 
         // without OOP, reuse a simple struct before making it complex
Graph
- Vertices // array of vertex
           // each vertex stores its edges; the graph doesn't need to

2。探路者结构

Node
- Parent // a link to the previous node
         // trace the links back to construct a path
- Depth // last node's depth + 1
- Vertex // the vertex hit by the pathfinder
Path
- Nodes // while parent is not null
        // add a node to this list
        // then read it backward