随机游走
我有一个问题搞清楚了这个问题的算法,不断尝试没有成功过几天,这里是一个什么即时试图获得知情同意:随机游走
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;
}
您需要更新row
和col
内循环。否则你总是会尝试从'A'的位置走路。
...一旦所有的4个方向都填满,你被困在一个无限循环
. . . . . . . B . . . E A C . . . D . .
即使你更新row
和col
内环路(和纠正错误==
) ,你必须处理一个问题:假设第一个点('A')是左上角,下一个随机方向是东,南,南,西,北。 ... 怎么办? :)
A B . F C . E D . . . .
它看起来像你破坏了你的switch语句,如果你试图在无效的方向走,但你无论如何增加您的柜台。尝试检查另一个随机的方向,如果发生。
它究竟在哪里破碎?
从我一眼就可以看到的是,你有It_that_walks位置会从巫婆它不能去任何地方机会:其中J后
A B C D .
. I J E .
. H G F .
?
没有必要为&& (box[row][col-1]= '.')
Allso,这是错误的(分配的,而不是比较),它应该是:&& (box[row][col-1]== '.')
(但你不需要它产品总数)
好吧,删除'&&(box [row] [col-1] =='。')'因为它不是必须的,但我无法弄清楚如何检查sourrounding元素是否被采用 – kdma 2011-04-04 18:06:54
这不是一个好主意如果你发现自己不能朝某个方向前进,那么“重新”随机数,因为如果运气不好,你会得到相同的号码两次(甚至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
}
}
感谢您的建议,我会尝试实现这种解决方案,当我重新开始:)并尝试明天完成它 – kdma 2011-04-04 19:30:46
当你在for循环。
- 画出一个可能的方向
int direction = rand()%4;
- 检查所有可能的方向,如果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;
}
}
- 如果有无效移动结束for循环>
if(i == 4) {
break;
}
- 否则写一个字母到表格单元格并更新行/列位置。
box[row][col] = letter;
而且这就是我所想的。这是贪婪的算法,所以你不需要任何优化(至少我没有看到任何在练习要求。
homework tag?:) – frnhr 2011-04-04 17:52:17
它在哪里卡住?你看到什么类型的输出? – Mikeb 2011-04-04 17:52:45
不知道有一个:)对不起,对于那些关心不是一个assignement只是测试我很低的问题解决能力:) – kdma 2011-04-04 17:53:27