10X10 网格阵列中的随机游走

问题描述 投票：0回答：3

我必须在 10X10 网格阵列中打印随机游走（字母 A-Z），向任一方向移动，只要移动不退出阵列且不与现有字母重叠。

我的输出是 

'.'
的完整网格，没有字母，保存 
'A'
来标记开始。

我看到了解决方案，并且关于条件测试和案例，我认为与我自己的没有什么区别。

我尝试注释掉测试并检查循环是否正确放置随机方向数和下一个字母，并且确实如此。然而，问题似乎出在测试上，但我坚持认为答案（至少在外观上）与我的没有不同。

这是我的程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

main()
{
    char t[10][10] = {0}, c;
    int i, j, dir;

    srand((unsigned) time(NULL));
    t[0][0] = 'A';

    for (c='B'; c <= 'Z'; c++) {
        dir = rand() % 4;
        // printf("%c\t%d\n\n", c, dir);  // Here proves to be correct if tests are omitted

        if (dir == 0 && i+1 < 10 && t[i+1][j] == '.')
            t[++i][j] = c;
        else if (dir == 1 && j+1 < 10 && t[i][j+1] == '.')
            t[i][++j] = c;
        else if (dir == 2 && i-1 >= 0 && t[i-1][j] == '.')
            t[--i][j] = c;
        else if (dir == 3 && j-1 >= 0 && t[i][j-1] == '.')
            t[i][--j] = c;
        else 
            break; 
    }

    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (t[i][j] == 0) 
                t[i][j] = '.';
            printf("%c ", t[i][j]);
        }
        printf("\n");
    }

    return 0;
}
c multidimensional-array random-walk
3个回答
2
投票

这里...

    char t[10][10] = {0}, c;

...您将 

t
的所有元素初始化为 0。

这里...

        if (dir == 0 && i+1 < 10 && t[i+1][j] == '.')
            t[++i][j] = c;
        else if (dir == 1 && j+1 < 10 && t[i][j+1] == '.')
            t[i][++j] = c;
        else if (dir == 2 && i-1 >= 0 && t[i-1][j] == '.')
            t[--i][j] = c;
        else if (dir == 3 && j-1 >= 0 && t[i][j-1] == '.')
            t[i][--j] = c;
        else 
            break;

...，虽然 

t
中除 
[0][0]
之外的所有元素仍为 0，但只有当目标单元格包含值 
'.'
（即 not 0）时，您才采取一步。因此，您将永远不要迈出一步。

此外，您显然假设 

i
和 
j
最初包含 0 和 0，但它们没有初始化，因此它们的值实际上是不确定的。该程序可能会碰巧表现得好像它们最初为零，但它决不限于这样做。将它们初始化为 0，对应于初始位置。

另请注意，如果无法在随机选择的方向上采取步骤，则会跳出循环。也许这是必需的行为，但由于您从角落开始，这意味着 50% 的时间您根本不会采取任何步骤，另外 25% 的时间您只会采取一步。也许你应该从中间的某个地方开始？或者只有当没有没有可以采取步骤的方向时才跳出循环？

1
投票

除了错误的 

main
签名（应该是 
int main(void)
）以及在具有不确定值时读取的变量 
i
和 
j
之外，还有两个主要问题：

  • 您从未将 
    '.'
    放入 
    t
    数组中，因此对 
    '.'
    的所有测试都会失败。

这是对“如果存在没有先前字母的现有路径，您可以继续而不中断”的回应：

  • 一旦你的循环尝试朝一个方向移动但失败了，它就会退出。还有其他三个方向可以尝试，因此您需要跟踪未经测试的方向。

示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

enum { down, right, up, left };
int moves[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main() {
    srand((unsigned)time(NULL));

    char t[10][10];
    memset(t, '.', sizeof t);  // fill the array with `.`
    int i = 0, j = 0;

    t[0][0] = 'A';

    for (char c = 'B'; c <= 'Z'; c++) {
        // candidate directions:
        char dirs[] = {down, right, up, left};
        int sel = 4;  // start with 4 possible
        for (;;) {
            int s = rand() % sel;  // pick one
            int dir = dirs[s];

            int ii = i + moves[dir][0];  // add the selected move to
            int jj = j + moves[dir][1];  // get a candidate position

            // is this position valid?
            if (ii >= 0 && ii < 10 && jj >= 0 && jj < 10 && t[ii][jj] == '.') {
                // it's valid, move there and put the letter in it
                i = ii;
                j = jj;
                t[i][j] = c;
                break;
            } else {
                // invalid position, remove this direction from the
                // candidates and reduce the number of directions to test
                if (--sel == 0) break;  // we got stuck, give up
                dirs[s] = dirs[sel];                
            }
        }
    }

    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            printf("%c ", t[i][j]);
        }
        putchar('\n');
    }
}
0
投票

正如其他人已经确定了代码的核心问题一样，看到一种消除使用“幻数”并允许通过编译时间常量轻松更改网格大小的实现可能会很有启发。

通过拥有四个可能方向的数组，我们可以shuffle以在确定的时间内获得随机方向，然后迭代这些方向，直到找到合适的移动方向（或者直到我们不）。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define WIDTH 10
#define HEIGHT 10
#define NUM_DIRS 4

enum Dir {
    UP, DOWN, LEFT, RIGHT
};

enum Edge {
    TOP_EDGE, BOTTOM_EDGE,
    LEFT_EDGE, RIGHT_EDGE
};

enum Dir dirs[NUM_DIRS] = {UP, DOWN, LEFT, RIGHT};

void shuffle_dirs();
bool at_edge(size_t x, size_t y, enum Edge e);
bool position_used(char grid[HEIGHT][WIDTH], size_t x, size_t y);

int main(void) {
    srand(time(NULL));

    char *alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    size_t x = 0;
    size_t y = 0;

    char grid[HEIGHT][WIDTH] = {0};

    grid[y][x] = alphabet[0];

    for (char *ch = &alphabet[1]; *ch; ch++) {
        shuffle_dirs();

        bool move_possible = false;

        for (size_t i = 0; i < NUM_DIRS && !move_possible; i++) {
            switch (dirs[i]) {
                case UP:
                if (at_edge(x, y, TOP_EDGE)) continue;
                if (position_used(grid, x, y - 1)) continue;
                grid[--y][x] = *ch;
                move_possible = true;
                break;

                case DOWN:
                if (at_edge(x, y, BOTTOM_EDGE)) continue;
                if (position_used(grid, x, y + 1)) continue;
                grid[++y][x] = *ch;
                move_possible = true;
                break;

                case LEFT:
                if (at_edge(x, y, LEFT_EDGE)) continue;
                if (position_used(grid, x - 1, y)) continue;
                grid[y][--x] = *ch;
                move_possible = true;
                break;

                case RIGHT:
                if (at_edge(x, y, RIGHT_EDGE)) continue;
                if (position_used(grid, x + 1, y)) continue;
                grid[y][++x] = *ch;
                move_possible = true;
                break;
            }
        }

        if (!move_possible) {
            fprintf(stderr, "Could not complete walk.\n");
            return 1;
        }
    }

    for (size_t i = 0; i < HEIGHT; i++) {
        for (size_t j = 0; j < WIDTH; j++) {
            if (!grid[i][j]) printf(".");
            else printf("%c", grid[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void shuffle_dirs() {
    for (size_t i = 0; i < NUM_DIRS - 1; i++) {
        size_t j = rand() % (NUM_DIRS - i - 1) + i + 1;

        enum Dir temp = dirs[i];
        dirs[i] = dirs[j];
        dirs[j] = temp;
    }
}

bool at_edge(size_t x, size_t y, enum Edge e) {
    switch (e) {
        case TOP_EDGE:
        return y == 0;

        case BOTTOM_EDGE:
        return y == HEIGHT - 1;

        case LEFT_EDGE:
        return x == 0;

        case RIGHT_EDGE:
        return x == WIDTH - 1;
    }
}

bool position_used(char grid[HEIGHT][WIDTH], size_t x, size_t y) {
    return grid[y][x] != 0;
}

运行示例：

$ ./a.out
ABC....RS.
.ED...PQTU
.FG..NOXWV
..HIJM.Y..
....KL.Z..
..........
..........
..........
..........
..........
$ ./a.out
AB........
DC..LMPQR.
EFGJKNOTS.
..HI.WVU..
.....XY...
......Z...
..........
..........
..........
..........
$ ./a.out
ABC..TU...
.ED.RSV...
GFOPQ.WX..
HINM...Y..
.JKL...Z..
..........
..........
..........
..........
..........
$ ./a.out
Could not complete walk.
$ ./a.out
AB.TUV....
.CDSRWZ...
.FEPQXY...
HGNO......
ILM.......
JK........
..........
..........
..........
..........
$ ./a.out
ABC.......
..D.......
..E.......
.GF.......
IH........
J.........
K.........
LM...UV...
.NO.STWX..
..PQR.ZY..
$ ./a.out
Could not complete walk.
$ ./a.out
ABEF......
.CDG......
...HI...ST
....J..QRU
....KNOP.V
....LM.YXW
.......Z..
..........
..........
..........
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.