一个关于迷宫的问题？请教了

Question

自己用C做了个迷宫，不过我想改进下：
从起点到目标点，不能转弯超过3次，否则就不能到达...
要怎么改呢？请教了#include "stdio.h"
#define maxi 15
#define maxj 15
/*一个普通的迷宫*/
int I_maze[maxi][maxj]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                1,1,1,1,1,1,0,0,0,0,0,1,1,1,0,
                0,1,0,0,0,1,1,0,0,0,0,1,0,1,0,
                0,1,0,0,0,0,1,1,1,0,0,1,0,1,0,
                0,0,0,1,1,1,1,0,0,1,1,1,0,1,0,
                0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,
                0,1,1,1,1,1,0,0,0,0,0,1,0,1,0,
                0,0,0,0,0,1,1,1,1,1,1,1,0,1,0,
                0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,
                0,0,0,1,1,1,1,0,0,1,1,1,0,1,0,
                0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,
                0,1,1,1,1,1,0,0,1,1,1,1,1,1,0,
                0,1,0,0,0,1,1,0,0,0,0,1,0,0,0,
                0,1,0,0,0,0,1,1,1,1,1,1,0,0,0,
                0,0,0,0,0,0,0,0,0,0,0,1,0,0,0};
int I_record[maxi][maxj];   /*一个辅助空间,用于记录走过的点*/
int n=0;         /*记录能找到出口的能有几条路*/void Suanfa(int i,int j)       /*求解函数*/
{
static int i1,j1;
if (I_maze[i][j]!=0 && I_record[i][j]!=1)
{
I_record[i][j]=1;
if (i==14 && j==11)        /*如果找到出口就记录（14，11为出口）,并输出*/
{
n++;
for (i1=0;i1<maxi;i1++)
{
    for (j1=0;j1<maxj;j1++)
        printf("%d,",I_record[i1][j1]);
    printf("\n");
}
printf("\n");
}
Suanfa(i,j+1);
I_record[i][j]=0;
I_record[i][j]=1;
Suanfa(i+1,j);
I_record[i][j]=0;
I_record[i][j]=1;
Suanfa(i-1,j);
I_record[i][j]=0;
I_record[i][j]=1;
Suanfa(i,j-1);
I_record[i][j]=0;
}
}
                    
void main()
{
    int i,j;
    for (i=0;i<maxi;i++)
        for (j=0;j<maxj;j++)
            I_record[i][j]=0;
    Suanfa(1,0);        /*输入起点*/
    printf("%d",n);
}

Answer 1

已经调试通过#include "stdio.h" 
#define maxi 15 
#define maxj 15 /*一个普通的迷宫*/ 
int I_maze[maxi][maxj]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 
1,1,1,1,1,1,0,0,0,0,0,1,1,1,0, 
0,1,0,0,0,1,1,0,0,0,0,1,0,1,0, 
0,1,0,0,0,0,1,1,1,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,1,0,0,0,0,0,0,0,1,0,1,0, 
0,1,1,1,1,1,0,0,0,0,0,1,0,1,0, 
0,0,0,0,0,1,1,1,1,1,1,1,0,1,0, 
0,0,0,0,0,0,1,0,0,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,0,0,1,0,0,0,0,0,0,0,1,0, 
0,1,1,1,1,1,0,0,1,1,1,1,1,1,0, 
0,1,0,0,0,1,1,0,0,0,0,1,0,0,0, 
0,1,0,0,0,0,1,1,1,1,1,1,0,0,0, 
0,0,0,0,0,0,0,0,0,0,0,1,0,0,0}; 
int I_record[maxi][maxj];  /*一个辅助空间,用于记录走过的点*/ int n=0;        /*记录能找到出口的能有几条路*/ int lasti[3] = {0,0,0};
int lastj[3] = {0,0,0};typedef struct Point
{
    int x;
int y;
} CPoint;
int Index = 0;
CPoint I_Posrecord[maxi * maxj];//读取迷宫路径
void findPath(int x, int y)
{
if (x==14 && y==11) 
{ I_Posrecord[Index].x = x;
        I_Posrecord[Index].y = y;
    Index ++;
}
for(int i = 0; i < Index; i++)
{
//该点被访问过；
if(x == I_Posrecord[i].x && y == I_Posrecord[i].y)
            return;     
}
if(I_record[x][y] == 1)
{
I_Posrecord[Index].x = x;
        I_Posrecord[Index].y = y;
    Index ++; findPath(x, y+1);
findPath(x-1, y);
findPath(x+1, y);
findPath(x, y-1);
}
}//在路径中搜索拐点
int findInflexion(int x, int y)
{
for(int i = 0; i < maxi * maxj; i++)
{
I_Posrecord[i].x = 0;
I_Posrecord[i].y = 0;
}
findPath(x,y);
int iInflexion = 0;
if(Index < 3)
return iInflexion; for(i = 0; i < Index-2; i++)
{
        if(I_Posrecord[i].x != I_Posrecord[i+2].x && I_Posrecord[i].y != I_Posrecord[i+2].y)
{
iInflexion++;
//printf("%d %d\n",I_Posrecord[i+1].x,I_Posrecord[i+1].y);

}

}
    Index = 0;
return iInflexion;
}void Suanfa(int i,int j)      /*求解函数*/ 
{ 
static int i1,j1; 
if (I_maze[i][j]!=0 && I_record[i][j]!=1) 
{ 
I_record[i][j]=1; 
if (i==14 && j==11)        /*如果找到出口就记录（14，11为出口）,并输出*/ 
{ 
n++; 
for (i1=0;i1 <maxi;i1++) 
{ 
for (j1=0;j1 <maxj;j1++) 
{
printf("%d,",I_record[i1][j1]); 
}
printf("\n"); 
} 
printf("\n"); 
int iInflexion = findInflexion(1,0);
printf("拐点数为:%d",iInflexion); //输出拐点数
printf("\n"); 
} 
//find inflexion
//int nCount = findInflexion(i,j); Suanfa(i,j+1); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i+1,j); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i-1,j); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i,j-1); 
I_record[i][j]=0; //回溯 
} 
} int main() 
{ 
    int i,j; 
    for (i=0;i <maxi;i++) 
        for (j=0;j <maxj;j++) 
            I_record[i][j]=0; 
Suanfa(1,0);        /*输入起点*/ 
printf("%d",n);  return 0;
}

Answer 2

根据lz的想法我对算法进行了优化，还有什么更好的优化方法，还希望继续探讨#include "stdio.h" 
#define maxi 15 
#define maxj 15 /*一个普通的迷宫*/ 
int I_maze[maxi][maxj]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 
1,1,1,1,1,1,0,0,0,0,0,1,1,1,0, 
0,1,0,0,0,1,1,0,0,0,0,1,0,1,0, 
0,1,0,0,0,0,1,1,1,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,1,0,0,0,0,0,0,0,1,0,1,0, 
0,1,1,1,1,1,0,0,0,0,0,1,0,1,0, 
0,0,0,0,0,1,1,1,1,1,1,1,0,1,0, 
0,0,0,0,0,0,1,0,0,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,0,0,1,0,0,0,0,0,0,0,1,0, 
0,1,1,1,1,1,0,0,1,1,1,1,1,1,0, 
0,1,0,0,0,1,1,0,0,0,0,1,0,0,0, 
0,1,0,0,0,0,1,1,1,1,1,1,0,0,0, 
0,0,0,0,0,0,0,0,0,0,0,1,0,0,0}; 
int I_record[maxi][maxj];  /*一个辅助空间,用于记录走过的点*/ 
int n=0;        /*记录能找到出口的能有几条路*/ typedef struct Point
{
    int x;
int y;
} CPoint;
int Index = 0;
CPoint I_Posrecord[maxi * maxj];//在路径中搜索拐点
int findInflexion(int x, int y, int Mode)
{
I_Posrecord[Index].x = x;
    I_Posrecord[Index].y = y;
Index +=Mode; if(Mode == -1)
return 0; int iInflexion = 0;
if(Index < 3)
return iInflexion; for(int i = 0; i < Index-2; i++)
{
        if(I_Posrecord[i].x != I_Posrecord[i+2].x && I_Posrecord[i].y != I_Posrecord[i+2].y)
{
iInflexion++;
//printf("%d %d\n",I_Posrecord[i+1].x,I_Posrecord[i+1].y);
}
}
return iInflexion;
}void Suanfa(int i,int j)      /*求解函数*/ 
{ 
static int i1,j1; 
if (I_maze[i][j]!=0 && I_record[i][j]!=1) 
{ 
I_record[i][j]=1; 
int iInflexion = findInflexion(i,j,1);
if(iInflexion > 13) // 如果大于设定的拐点数，停止搜索
{
I_record[i][j]=0;
return;
} if (i==14 && j==11)        /*如果找到出口就记录（14，11为出口）,并输出*/ 
{ 
n++; 
for (i1=0;i1 <maxi;i1++) 
{ 
for (j1=0;j1 <maxj;j1++) 
{
printf("%d,",I_record[i1][j1]); 
}
printf("\n"); 
} 

printf("\n"); 
//int iInflexion = findInflexion(1,0);
printf("拐点数为:%d",iInflexion); //输出拐点数
printf("\n"); 
} 
Suanfa(i,j+1); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i+1,j); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i-1,j); 
//I_record[i][j]=0; 
//I_record[i][j]=1; 
Suanfa(i,j-1); 
I_record[i][j]=0; //回溯 
findInflexion(i,j,-1);//返回上一个点
} 
} int main() 
{ 
    int i,j; 
    for (i=0;i <maxi;i++) 
        for (j=0;j <maxj;j++) 
            I_record[i][j]=0; 
Suanfa(1,0);        /*输入起点*/ 
printf("%d",n);  return 0;
}

Answer 3

发觉有点问题啊？
我改下图的某个点，然后改下不同起点，不同终点
发现出错了，还有一条路4个弯走完，我设8个拐角停止搜索和7个拐角停止搜索
结果竟然不一样。。为啥？
大概我照你的修改下数据如下
#include "stdio.h" 
#define maxi 15 
#define maxj 15 /*一个普通的迷宫*/ 
int I_maze[maxi][maxj]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 
1,1,1,1,1,1,0,0,0,0,0,1,1,1,0, 
0,1,0,0,1,1,1,0,0,0,0,1,0,1,0, 
0,1,0,0,0,0,1,1,1,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,1,0,0,0,0,0,0,0,1,0,1,0, 
0,1,1,1,1,1,0,0,0,0,0,1,0,1,0, 
0,0,0,0,0,1,1,1,1,1,1,1,0,1,0, 
0,0,0,0,0,0,1,0,0,0,0,1,0,1,0, 
0,0,0,1,1,1,1,0,0,1,1,1,0,1,0, 
0,0,0,0,0,1,0,0,0,0,0,0,0,1,0, 
0,1,1,1,1,1,0,0,1,1,1,1,1,1,0, 
0,1,0,0,0,1,1,0,0,0,0,1,0,0,0, 
0,1,0,0,0,0,1,1,1,1,1,1,0,0,0, 
0,0,0,0,0,0,0,0,0,0,0,1,0,0,0}; 
int I_record[maxi][maxj];  /*一个辅助空间,用于记录走过的点*/ 
int n=0;        /*记录能找到出口的能有几条路*/ typedef struct Point 
{ 
    int x; 
int y; 
} CPoint; 
int Index = 0; 
CPoint I_Posrecord[maxi * maxj]; //在路径中搜索拐点 
int findInflexion(int x, int y, int Mode) 
{ 
I_Posrecord[Index].x = x; 
    I_Posrecord[Index].y = y; 
Index +=Mode; 

if(Mode == -1) 
return 0;  int iInflexion = 0; 
if(Index < 3) 
return iInflexion;  for(int i = 0; i < Index-2; i++) 
{ 
   if(I_Posrecord[i].x != I_Posrecord[i+2].x && I_Posrecord[i].y != I_Posrecord[i+2].y) 
{ 
iInflexion++; 
//printf("%d %d\n",I_Posrecord[i+1].x,I_Posrecord[i+1].y); 
} 
} 
return iInflexion; 
} void Suanfa(int i,int j)      /*求解函数*/ 
{ 
static int i1,j1; 
if (I_maze[i][j]!=0 && I_record[i][j]!=1) 
{ 
I_record[i][j]=1; 
int iInflexion = findInflexion(i,j,1); 
if(iInflexion >8) // 如果大于设定的拐点数，停止搜索 
{ 
I_record[i][j]=0; 
return; 
} if (i==4 && j==4)        /*如果找到出口就记录（14，11为出口）,并输出*/ 
{ 
n++; 
for (i1=0;i1 <maxi;i1++) 
{ 
for (j1=0;j1 <maxj;j1++) 
{ 
printf("%d,",I_record[i1][j1]); 
} 
printf("\n"); 
}  printf("\n"); 
//int iInflexion = findInflexion(1,0); 
printf("::::::%d\n",iInflexion); //输出拐点数  
} 
Suanfa(i,j+1); 
 
Suanfa(i+1,j); 
 
Suanfa(i-1,j);  Suanfa(i,j-1); 
I_record[i][j]=0; //回溯 
findInflexion(i,j,-1);//返回上一个点 
} 
} int main() 
{ 
    int i,j; 
    for (i=0;i <maxi;i++) 
        for (j=0;j <maxj;j++) 
            I_record[i][j]=0; 
Suanfa(1,3);        /*输入起点*/ 
// printf("%d\n",Index);
// Index=0;
// Suanfa(4,4);
// Index=0;
// Suanfa(14,11);
// printf("%d\n",Index); printf("%d",n);

Answer 4

对于还有一条路4个弯走完，我设8个拐角停止搜索和7个拐角停止搜索 这个问题，我已找出原因
if(iInflexion >8) // 如果大于设定的拐点数，停止搜索 
{ 
I_record[i][j]=0; 
//此处应该加上返回上一点
findInflexion(0,0,-1);//返回上一个点 
return; 
} 对于你提出的另一个bug不知道你改的是哪个点，能不能更详细的描述一下。另外我写的部分中的这一句有点问题
findInflexion(i,j,-1);//返回上一个点 
应改为findInflexion(0,0,-1);//呵呵

Answer 5

OK了..好象没有啥问题了~
应该是由于这句findInflexion(i,j,-1)错误而造成的...
连连看已经弄好了~
不过我有一个优化想法，稍后和你说

Answer 6

搜索路径的时候修改一下，
大概如下：
if (i>出口Y坐标)
if (j>出口X坐标)
{
Suanfa(i-1,j); 
Suanfa(i,j-1); 
Suanfa(i+1,j);  
Suanfa(i,j+1); 
}
else 
{
Suanfa(i-1,j); 
Suanfa(i,j+1); 
Suanfa(i+1,j);  
Suanfa(i,j-1);
}
else 
if (j>出口X坐标)
{
Suanfa(i+1,j); 
Suanfa(i,j-1); 
Suanfa(i-1,j);  
Suanfa(i,j+1);
}
else 
{  
Suanfa(i+1,j); 
Suanfa(i,j+1); 
Suanfa(i-1,j);  
Suanfa(i,j-1);
}
这样会根据此时的坐标相对于出口的坐标而选择先搜索的方面
应该会更优些吧？