隨機遊走

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; 

而且這就是我所想的。這是貪婪的算法，所以你不需要任何優化（至少我沒有看到任何在練習要求。