随机游走

Question

我有一个问题搞清楚了这个问题的算法，不断尝试没有成功过几天，这里是一个什么即时试图获得知情同意：

http://i.stack.imgur.com/X70nX.png

这里是我的代码尝试了许多不同的解决方案，但总是卡在同一点:(对不起，混合语言的重要组成部分是英文）

ps 即时通讯不应该使用函数来解决这个问题只有循环和数组。

编辑 经过多次修复后，它做的步行，但很少崩溃 任何想法？

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

int main(void){ 

char box[10][10]; 
int i,j; 
int move,row,col; 
char letter='A'; 
srand(time(NULL)); 

printf("\n\tSTART\n\n"); 

for(i=0;i < 10 ;i++)/* righe */ 
{ 
for(j=0;j < 10;j++) /* colonne */ 
{ 
    box[i][j] = '.'; /* assegno . a tutti gli elementi dell array */ 
    if(j == 9) 
    printf("%c%c\n", box[i][j]); /* giustifico ogni 10 elementi dell array j(0-9) */ 
    else 
    printf("%c%c", box[i][j]); 
    } 
} 


/* LETS START */ 

printf("\n\n Inizia il gioco\n\n"); 

/* random place to start */ 

row = rand() % 9; 
col = rand() % 9; 
box[row][col]= 'A'; 


while(letter <= 'Z') 
{ 
if(box[row+1][col] == '.' || box[row-1][col] == '.' || box[row][col+1] == '.' || box[row][col-1] == '.') 
{ 
move=rand() % 4; 
switch(move){ 
       case 0: /* Going UP */ 
        if((row != 0) && (box[row-1][col] == '.')) 
        { 
          box[row-1][col]=++letter; 
          box[row--][col]; 
        }else{ 
          move=rand() % 4; 
          } 
       case 1:/* Going Down */ 
        if((row != 9) && (box[row+1][col] == '.')) 
        { 
          box[row+1][col]=++letter; 
          box[row++][col]; 
        }else{ 
         move=rand() % 4; 
         } 
       case 2: /*Going Left */ 
        if((col != 0) && (box[row][col-1] == '.')) 
        { 
          box[row][col-1]=++letter; 
          box[row][col--]; 
        }else{ 
         move=rand() % 4; 
         } 
       case 3: /* Going Right */ 
        if((col != 9) && (box[row][col+1] == '.')) 
        { 
          box[row][col+1]=++letter; 
          box[row][col++]; 
        }else{ 
         move=rand() % 4; 
         } 
       } 
}else{ 
     printf("\n\nBloccato a %c\n\n", letter); 
     break; 
} 
} 


/* FINE */ 

for(i=0;i<10;i++)/* righe */ 
{ 
for(j=0;j<10;j++) /* colonne */ 
{ 
    if(j == 9) 
    printf("%c%c\n", box[i][j]); /* giustifico ogni 10 elementi dell array j(0-9) */ 
    else 
    printf("%c%c", box[i][j]); 
} 
} 
return 0; 
} 

Answer 1

您需要更新row和col内循环。否则你总是会尝试从'A'的位置走路。

...一旦所有的4个方向都填满，你被困在一个无限循环

 
. . . . . 
. . B . . 
. E A C . 
. . D . . 

---

即使你更新row和col内环路（和纠正错误==） ，你必须处理一个问题：假设第一个点（'A'）是左上角，下一个随机方向是东，南，南，西，北。 ... 怎么办？ :)

 
A B . 
F C . 
E D . 
. . . 

Answer 2

它看起来像你破坏了你的switch语句，如果你试图在无效的方向走，但你无论如何增加您的柜台。尝试检查另一个随机的方向，如果发生。

Answer 3

它究竟在哪里破碎？

从我一眼就可以看到的是，你有It_that_walks位置会从巫婆它不能去任何地方机会：其中J后

A B C D . 
. I J E . 
. H G F . 

？

没有必要为&& (box[row][col-1]= '.')

Allso，这是错误的（分配的，而不是比较），它应该是：&& (box[row][col-1]== '.')（但你不需要它产品总数）

Answer 4

这不是一个好主意如果你发现自己不能朝某个方向前进，那么“重新”随机数，因为如果运气不好，你会得到相同的号码两次（甚至3次或4次或更多次） - 所以即使你生成了4个随机数，他们都失败了，那并不意味着你被困住了。

可以通过产生一个数字，并试图从它开始的所有4个可能的方向解决这一问题：如果所述随机数发生器返回0

：检查0，1，2，3

如果随机数发生器返回的1：检查1，2，3，0

如果随机数发生器返回2：检查2，3，0,1

如果随机数发生器返回的3：CH ECK 3，0，1，2

通过下面的代码实现：

desired_move = rand(); 
success = 0; 
for (i = 0; i < 4 && !success; ++i) 
{ 
    move = (desired_move + i) % 4; 
    switch (move) 
    { 
    case 0: // Go up 
     if (row > 0 && box[row - 1][col] == '.') 
     { 
      row = row - 1; 
      success = 1; 
     } 
     break; 
    case 1: // Go down 
     ... 
    } 
} 
if (!success) // Tried all 4 directions but failed! You are stuck! 
{ 
    goto START_OVER; // or whatever else 
} 

注意，这个算法是不是很随意的：如果你不能上去，还有就是你去一个更大的机会比右或左。如果你想修复它，你可以选择4个方向的随机排列，而不是顺序检查方向：

const int permutation_table[24][4] = { 
    {0, 1, 2, 3}, 
    {0, 1, 3, 2}, 
    {0, 2, 1, 3}, 
    ... 
    {3, 2, 1, 0} 
}; 
index = rand() % 24; 
for (i = 0; i < 4; ++i) 
{ 
    move = permutation_table[index][i]; 
    switch (move) { 
    ... // As above 
    } 
} 

Answer 5

当你在for循环。

1. 画出一个可能的方向

int direction = rand()%4; 

1. 检查所有可能的方向，如果drawed一个是无效的（不是数组或不是 “”）

int i=-1; 
while(++i < 4) 
{ 
    switch(direction) 
    { 
     case 0: 
      if(row-1 >= 0 && box[row-1][col] == '.') { 
       --row; 
       i = -1;  
      } 
      break; 
     case 1: 
      if(col+1 < 10 && box[row][col+1] == '.') { 
       ++col; 
       i = -1;  
      } 
      break; 
     case 2: 
      if(row+1 < 10 && box[row+1][col] == '.') { 
       ++row; 
       i = -1; 
      } 
      break; 
     case 3: 
      if(col-1 >= 0 && box[row][col-1] == '.') { 
       --col; 
       i = -1; 
      } 
      break; 
    } 

    if(i != -1) { 
     direction = (direction+1)%4; 
    } 
    else { 
     break; 
    } 
} 

1. 如果有无效移动结束for循环>

if(i == 4) { 
    break; 
} 

1. 否则写一个字母到表格单元格并更新行/列位置。

box[row][col] = letter; 

而且这就是我所想的。这是贪婪的算法，所以你不需要任何优化（至少我没有看到任何在练习要求。