C的迷宫问题

1回溯算法

7． 迷宫问题

给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。

输入数据：’’表示空格；’X’表示墙。

程序如下：

#include <stdioh>

#include <mathh>

void search(int,int);

int canplace(int,int);

void readdata(); //读入数据

void printresult(); //打印结果

int a[20][20]; //a数组存放迷宫

int s,t;

int main()

{

int row, col;

readdata();

row=s/20;

col=s%20;

search(row,col); //递归搜索

printresult();

}

void search(int row, int col)

{

int r,c;

a[row][col]=1;

r=row; //左

c=col-1;

if(canplace(r,c)) //判断(r,c)位置是否已经走过

search(r,c); //递归搜索(r,c)

r=row+1; //下

c=col;

if(canplace(r,c)) //判断(r,c)位置是否已经走过

search(r,c); //递归搜索(r,c)

r=row; //右

c=col+1;

if(canplace(r,c)) //判断(r,c)位置是否已经走过

search(r,c); //递归搜索(r,c)

r=row-1; //上

c=col;

if(canplace(r,c)) //判断(r,c)位置是否已经走过

search(r,c); //递归搜索(r,c)

}

void printresult()

{

int i,j;

for(i=0;i<20;i++)

{

for(j=0;j<20;j++)

printf("%3d",a[i][j]);

printf("\n");

}

}

void readdata()

{

int i,j;

for(i=0;i<20;i++)

{

for(j=0;j<20;j++)

scanf("%d",&a[i][j]);

}

}

int canplace(int row, int col)

{

if(row>=0&&row<20&&col>=0&&col<20&&a[row][col]==0)

return 1;

else

return 0;

}

2搜索算法

如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。

抱歉，图案粘贴不上

本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下：

#include<stdioh>

void readdata(); //读入数据

void init(); //初始化

int search(); //广搜，并在每一个可到达的每一个空格出填上最小步数

int emptyopen(); //判栈是否为空：空：1；非空：0。

int takeoutofopen(); //从栈中取出一个元素，并把该元素从栈中删除

int canmoveto(int,int,int,int,int); //判能否移动到该方向，并带回坐标(r,c)

int isaim(int row, int col); //判断该点是否是目标

int used(int,int); //判断该点是否已经走过

void addtoopen(int,int); //把该点加入到open表

int a[12][12]; //a存放迷宫，0表示空格，-2表示墙。

//广搜时，未找到目标以前到达的空格，填上到达该点的最小步数

int n; //n为迷宫边长，注：若大于12，必须修改一些参数，如a的大小

int open[20],head,tail,openlen=20; //open表

int s,t; //起点和终点

int main()

{

int number;

readdata(); //读取数据

init(); //初始化

number=search(); //广搜并返回最小步数

printf("%d",number); //打印结果

}

int search()

{

int u, row, col, r, c, i, num;

while(!emptyopen()) //当栈非空

{

u=takeoutofopen(); //从栈中取出一个元素，并把该元素从栈中删除

row=u/n; //计算该点的坐标

col=u%n;

num=a[row][col]; //取得该点的步数

for(i=0;i<4;i++)

{

if(canmoveto(row,col,&r,&c,i)) //判能否移动到该方向，并带回坐标(r,c)

{

if(isaim(r,c)) //如果是目标结点

return(num+1); //返回最小步数

if(!used(r,c)) //如果(r,c)还未到达过

{

a[r][c]=num+1; //记录该点的最小步数

addtoopen(r,c); //把该点加入到open表

}

}

}

}

}

int emptyopen()

{

if(head==tail)

return(1);

else

return(0);

}

int takeoutofopen()

{

int u;

if(head==tail)

{

printf("errer: stack is empty");

return(-1);

}

u=open[head++];

head=head%openlen;

return(u);

}

int canmoveto(int row, int col, int p, int q, int direction)

{

int r,c;

r=row;

c=col;

switch(direction)

{

case 0: c--; //左

break;

case 1: r++; //下

break;

case 2: c++; //右

break;

case 3: r--; //上

}

p=r;

q=c;

if(r<0||r>=n||c<0||c>=n) //如果越界返回0

return(0);

if(a[r][c]==0) //如果是空格返回1

return(1);

return(0); //其余情况返回0

}

int isaim(int row, int col)

{

if(rown+col==t)

return(1);

else

return(0);

}

int used(int row, int col)

{

if(a[row][col]==0) // 0表示空格

return(0);

else

return(1);

}

void addtoopen(int row, int col)

{

int u;

u=rown+col;

open[tail++]= u;

tail=tail%openlen;

}

void readdata()

{

int i,j,row,col;

char str[20];

scanf("%d",&n);

scanf("%d%d",&row,&col); //起点坐标

s=rown+col;

scanf("%d%d",&row,&col); //终点坐标

t=rown+col;

gets(str);

for(i=0;i<n;i++)

{

gets(str);

for(j=0;j<n;j++)

if(str[j]=='')

a[i][j]=0; //0表示空格

else

a[i][j]=-2; //－2表示墙

}

}

void init()

{

head=0;

tail=1;

open[0]=s;

}

测试数据如下：

12 10 7 1 8

XXXXXXXXXXXX

XXXXX

XXXXX

XXXXXXXX

XXXX

XXXXXXXXXXX

XXXX

XXXXXXXX

XXX

XXXXXXXXX

XXXXXXXXXX

XXXXXXXXXXXX

#include <stdioh> #include <memh> void main() { int a[100][100]; //0:blocked 1:passage 2:finish -1:visited; int b[10000][2]; int m=0,n=0; int sttop=0; int i,j,k,l; memset(a,0,sizeof(a)); printf("Please Input m,n:"); scanf("%d%d",&m,&n); printf("Input the start:"); scanf("%d%d",&i,&j); b[0][0]=i-1; b[0][1]=j-1; printf("Input the Map:\n"); for (i=0;i<m;i++) for (j=0;j<n;j++) { scanf("%d",&a[i][j]); } printf("Input the Finish:"); scanf("%d%d",&i,&j); a[i-1][j-1]=2; i=b[sttop][0];j=b[sttop][1]; a[i][j]=-1; while (sttop!=-1) { if (i>0) { //can up if (a[i-1][j]==1) { a[--i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i-1][j]==2) { b[++sttop][0]=--i; b[sttop][1]=j; break; } } if (i<m-1) { //can up if (a[i+1][j]==1) { a[++i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i+1][j]==2) { b[++sttop][0]=++i; b[sttop][1]=j; break; } } if (j>0) { //can left if (a[i][j-1]==1) { a[i][--j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j-1]==2) { b[++sttop][0]=i; b[sttop][1]=--j; break; } } if (j<m-1) { //can up if (a[i][j+1]==1) { a[i][++j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j+1]==2) { b[++sttop][0]=i; b[sttop][1]=j++; break; } } sttop--; } if (sttop+1) { for (i=0;i<sttop;i++) printf("(%d,%d)->",b[i][0]+1,b[i][1]+1); printf("(%d,%d)\n",b[i][0]+1,b[i][1]+1); } else printf("Can't Reach The Finish Spot!\n"); return; } 用非嵌套的方法做的栈，起点 终点自己定 输入数据规则如下： 先输入m n（m为行数，n为列数） 再输入起点(最左上角为(1,1)（前者行号，后者列号）则输入"1 1"（不含引号）其他依次类推) 再输入地图(0为被阻挡，1为通路)（起点被默认为通路，无论输入0还是1） 再输入终点（规则和起点一样） 回车后出结果，结果的表达方式以(x,y)->(x,y)->->(x,y)（坐标任以1，1为左上角） 或者Can't Reach The Finish Spot! 呈现 其他的修改的话可以随便咯（规模m,n<=100，太大栈放不下了）

遍历的时候没有把已经尝试过的地方做标记

int explore(int i,int j,int i0,int j0)

{

int k=0,i1=0,j1=0;

int changes[4][2]=

{

{-1,0},

{1,0},

{0,-1},

{0,1}

};

if(i==n&&j==m)

{

return 1;

}

else

{

matrix[i][j] = -1;

for(k=0;k<=3;k++)

{

int ti = i+changes[k][0];

int tj = j+changes[k][1];

if(matrix[ti][tj] == -1)

continue;

i1=ti;

j1=tj;

if((i1!=i||j1!=j)&&(isValidChoice(i1,j1)==1))

{

if(explore(i1,j1,i,j)==1)

{

return 1;

}

}

}

return 0;

}

}

以上就是关于C的迷宫问题全部的内容，包括:C的迷宫问题、C语言迷宫问题，用栈来做、c语言挑错 迷宫问题 下附代码 在线等等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！