c - “随机游走”计划提前终止

Question

这是我对这个问题的代码：

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

#define N 10

int main()
{
int i,move,move_count,row,col;
char ch = 'A',a[N][N];

for(row = 0; row < N; row++)
   for(col = 0; col < N; col++)
      a[row][col] = '.';

srand(time(NULL));
row = rand()%10;
col = rand()%10;
a[row][col] = ch;

for(i = 0; i < 26; i++)
{
    move = rand() % 4;
    move_count = 0;
    if(move == 0 && move_count < 4)                   //down
    {
        if(row+1 < 10 && a[row+1][col] == '.')
        {
           ch = ch + 1;    
           a[row+1][col] = ch;
           row += 1; 
        }
        else 
        {
           move = 2; 
           move_count++;
        }
    }

    if(move == 2 && move_count < 4)              //up
    {
        if(row-1 > 0 && a[row - 1][col] == '.')
        {
            ch = ch + 1; 
            a[row-1][col] = ch;
            row -= 1;
        }
        else 
        {
           move = 1; 
           move_count++;
        }
    }

    if(move == 1 && move_count < 4)             //left
    {
        if(col-1 > 0 && a[row][col-1] =='.')
        {
            ch = ch + 1; 
            a[row][col-1] = ch;
            col -= 1;
        }
        else 
        {
           move = 3; 
           move_count++;
        }
    }

    if(move == 3 && move_count < 4)             //right
    {
        if(col+1 < 10 && a[row][col+1] == '.')
        {
            ch = ch + 1; 
            a[row][col+1] = ch;
            col += 1;
        }
        else 
        {
           move = 0; 
           move_count++;
        }
    }
    if(move_count == 4)
    break;

}

for(row = 0; row < N; row++)
{
    for(col = 0; col < N; col++)
       printf("%c",a[row][col]);
    printf("\n");
}                                  
getch();
}

在执行时，有时它会在不违反条件的情况下提前终止。这(b)是提前终止的一些截图；

在第一个 o/p 中可以很容易地看到，它终止于，V而在第二个它终止于Y，尽管在这两种情况下都可以进一步移动。知道如何摆脱这个吗？

已编辑
经过我的不懈努力，我已经更正了这段代码（是的，没有使用内部循环！）。感谢 Thomas Padron-McCarthy&Ilmari Karonen提供建议。
编辑代码：

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

#define N 10

int main()
{
int i,move,move_count,row,col,seed=4;
char ch = 'A',a[N][N];

for(row = 0; row < N; row++)
   for(col = 0; col < N; col++)
      a[row][col] = '.';

srand((unsigned)seed);
//srand(time(NULL));
row = 0;//rand()%10;
col = 0;//rand()%10;
a[row][col] = ch;

for(i = 0; i < 26;)
{
    move = rand() % 4;

    if(move == 0)                                   //down
    {
        if(row+1 < N && a[row+1][col] == '.')
        {

           a[++row][col] = ++ch;
           i++;
        }

    }

    else if(move == 2)                              //up
    {
        if(row-1 >= 0 && a[row - 1][col] == '.')
        {
            a[--row][col] = ++ch;
            i++;
        }

    }

    else if(move == 1)                              //left
    {
        if(col-1 >= 0 && a[row][col-1] =='.')
        {
            a[row][--col] = ++ch;
            i++;
        }

    }

    else if(move == 3)                              //right
    {
        if(col+1 < N && a[row][col+1] == '.')
        {
            a[row][++col] = ++ch;
            i++;
        }

    }
    if((a[row+1][col]!='.'||row==9) && (a[row - 1][col]!='.'||row==0) && 
        (a[row][col-1]!='.'||col==0 )&& (a[row][col+1]!='.'||col==9) || i==25)
        break;        

}

for(row = 0; row < N; row++)
{
    for(col = 0; col < N; col++)
       printf("%c ",a[row][col]);
    printf("\n");
}                                  
return 0;

}

Answer 1

你for(i = 0; i < 26; i++)没有内部循环。

这意味着您将有 26次尝试，而不是 26次移动。

您需要一个内部循环，它将尝试向随机方向前进，并且只有在检查了所有 4 个方向后才会退出。

注意：计算尝试次数 ( move_count) 是行不通的，因为rand它可以为您多次提供相同的方向。

Answer 2

您的问题是，如果原始方向被阻止，您正在增加移动方向，但递增过程最多只能达到 3；之后它不会回绕到 0。因此，例如，如果您选择的原始随机方向是 2，并且方向 2 和 3 都被阻止，那么您永远不会尝试方向 0 和 1。

两个明显的解决方案（这也保证了有效方向的均匀随机选择，与您的方法不同，它偏向于数字上的第一个非阻塞方向）是：

• 首先检查是否至少有一个有效的移动方向，如果是，请无限期地选择随机方向，直到找到一个有效的方向，或者

• 首先列出所有有效的移动方向，然后从中选择一个随机元素。

第二种方法实现起来稍微（但不是很多）复杂，但它也应该更快，至少在许多相邻方块已经被填充的情况下。

Answer 3

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

#define N 10

int main(void){
    int i, row, col;
    char ch = 'A',a[N][N];

    for(row = 0; row < N; row++)
        for(col = 0; col < N; col++)
            a[row][col] = '.';

    srand(time(NULL));
    row = rand()%10;
    col = rand()%10;
    a[row][col] = ch;

    for(i = 1; i < 26; i++){//already put 'A'
        enum { down, left, up, right };//0,1,2,3
        int move[] = {0,1,2,3};//Candidate in the moving direction
        int move_count, n;
        n = rand() % 4;//start direction
        move_count = 0;

        while(move_count<4){
            int gone = 0;
            n = (n + move_count) % 4;
            switch(move[n]){
            case  down:
                if(row+1 < 10 && a[row+1][col] == '.'){
                    a[++row][col] = ++ch;
                    gone = 1;//I was able to go forward.
                }
                break;
            case up:
                if(row-1 > 0 && a[row - 1][col] == '.'){
                    a[--row][col] = ++ch;
                    gone = 1;
                }
                break;
            case left:
                if(col-1 > 0 && a[row][col-1] =='.'){
                    a[row][--col] = ++ch;
                    gone = 1;
                }
                break;
            case right:
                if(col+1 < 10 && a[row][col+1] == '.'){
                    a[row][++col] = ++ch;
                    gone = 1;
                }
                break;
            }
            if(gone) break;
            ++move_count;//Number of times that I tried for a destination
        }
        if(move_count == 4){
            printf("No longer able to move\n");//need backtrack
            break;//give up!
        }
    }

    for(row = 0; row < N; row++){
        for(col = 0; col < N; col++)
            printf("%c",a[row][col]);
        printf("\n");
    }
    return 0;
}