0

我正在尝试解决一个问题，因为我有一个包含迷宫的输入文件，我知道如何解决迷宫但我不知道如何储存迷宫。我不能将它存储在 char 数组中，因为该文件最多可以包含 20 亿个字符。我不知道如何在不爆炸缓冲区的情况下存储文件...使用 read 命令读取文件（不允许使用 fread）。

4

3 回答 3

2

从您的描述听起来您需要阅读迷宫，然后存储已解决的迷宫的副本。

假设您的迷宫将存储为一个二维字符数组，其中一个字符代表墙砖 - 例如'*'-，另一个是开放空间 - 例如''-，所以是一个 8 x 8 的小迷宫可能看起来像这样：

    ** *
    * *
    * * * *
    * * *
    * *** **
    * * *
    *** ***
    *** ***

然后你需要做你的解决，并用一个 char 存储迷宫，代表解决它所遵循的路径的步骤。其中 - 假设 char 是 '+' ，它将如下所示：

    *****+*
    *++++++*
    *+ *** *
    *+ * *
    **+*** **
    *+++* *
    ***+****
    ***+****

是我——并且是使用少量内存的目标——我要做的第一件事是将迷宫转换为位，其中星号将由 1 表示，空格由 0 表示。生成的地图将小 8 倍。然后我会做我的解决，但就像我不能在地图中存储'+' - 位只能有 2 个值 - 我会改为将每个步骤的位置存储在链表上。然后我将通过读取地图的每个位置并在列表中检查它来保存输出迷宫，如果它在那里我将输出一个“+”，否则我将检查该位并输出“*”如果它是 1，并且' ' 如果它是 0。

就像这是一个大学项目，我不会在这里给你所有的代码——因为你应该自己写——但我会给你一些关于一些未优化代码形式的足够线索。;-) 

struct pos {
    int x,y;
    struct pos *next;
};

struct pos *step_list=NULL;

#define MAZE_WIDTH_BITS  ((MAZE_WIDTH + 7) / 8)

unsigned char bitmaze[MAZE_HEIGHT][MAZE_WIDTH_BITS];

int getbit(int x,int y)
{
    unsigned char v = bitmaze[y][(x / 8)];


    v >>= 7 - (x % 8);
    return (v & 1);
}


void save_maze(FILE *fp)
{
    int x,y,found;
    struct pos *cur_step;

    for(y=0;y<MAZE_HEIGHT;y++)
    {
        for(x=0;x<MAZE_WIDTH;x++)
        {
            found=0;
            cur_step=step_list;
            while(cur_step && !found)
            {
                if(cur_step->x==x && cur_step->y==y)
                     found=1;
                else
                    cur_step=cur_step->prox;
            }
            if(found)
                fputc('+',fp);
            else
                fputc( getbit(x,y) ? '*' : ' ',fp);
        }
    }
}

希望这对您有所帮助。吉列莫迪奥。

于 2013-09-30T21:34:50.250 回答
0

为什么不为 2000000000 字符数组分配内存？唯一的限制是你的电脑内存。如果留有足够的连续地址空间，则没有问题。

你可以尝试类似的东西char *my_maze = (char*) malloc((2000000000 * sizeof(char)));

于 2013-09-30T17:42:21.947 回答
0

好吧，您可以使用一个链表，其中每个节点都包含一个字符，这将占用大量空间，但它会做到

于 2013-09-30T17:50:47.040 回答