我有一个问题找出这个问题的算法，已经尝试了几天没有成功，这里是我试图获得的PIC:
https://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("ntSTARTnn");
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%cn", box[i][j]); /* giustifico ogni 10 elementi dell array j(0-9) */
else
printf("%c%c", box[i][j]);
}
}
/* LETS START */
printf("nn Inizia il gioconn");
/* 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("nnBloccato a %cnn", letter);
break;
}
}
/* FINE */
for(i=0;i<10;i++)/* righe */
{
for(j=0;j<10;j++) /* colonne */
{
if(j == 9)
printf("%c%cn", box[i][j]); /* giustifico ogni 10 elementi dell array j(0-9) */
else
printf("%c%c", box[i][j]);
}
}
return 0;
}
需要在循环内更新row和col。否则你会一直尝试从'A'的位置开始走。
…一旦四个方向都被填满，你就陷入了无限循环
<>之前. . . . .． . 选B。。E a c。． . 解析:选D。之前即使当你在循环内更新row和col(并纠正==错误)，你必须处理一个问题:假设第一个点(' a ')是左上角，下一个随机方向是东，南，南，西和北. ...现在怎么办呢?:)
"滚动"不是一个好主意。当你发现你不能往某个方向走的时候，随机数，因为如果你运气不好，你会得到同样的数字两次(甚至3次、4次或更多次)——所以即使你生成了4个随机数，它们都失败了，这并不意味着你被困住了。
你可以通过生成一个数字，并尝试从它开始的所有4个可能的方向来解决这个问题:
如果随机数生成器返回0:检查0、1、2、3
如果随机数生成器返回1:检查1,2,3,0
如果随机数生成器返回2:检查2,3,0,1
如果随机数生成器返回3:检查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
}
}
当你进入for循环时
- 画一个可能的方向
int direction = rand()%4;
- 检查所有可能的方向，如果绘制的一个是无效的(不是在数组或不是一个"。")
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;
}
- 否则写信给表格单元格并更新行/col位置
box[row][col] = letter;
…我想就这些了。这是贪婪算法，所以你不需要任何优化(至少我没有看到任何在练习要求。
如果您尝试朝着无效的方向前进，那么看起来您正在打破switch语句，但无论如何您都要增加计数器。如果发生这种情况，请尝试检查另一个随机方向
它到底在哪里断裂?
从我一眼看到的是，你有机会It_that_walks从它不能去任何地方的位置:
A B C D .
. I J E .
. H G F .
J后面在哪里?
不需要&& (box[row][col-1]= '.')
同样，这是错误的(赋值而不是比较)，它应该是:&& (box[row][col-1]== '.')(但你不需要全部)