7． 迷宮問題
給壹個20×20的迷宮、起點坐標和終點坐標，問從起點是否能到達終點。
輸入數據：’.’表示空格；’X’表示墻。
程序如下：
#include <stdio.h>
#include <math.h>
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<stdio.h>
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(row*n+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=row*n+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=row*n+col;
scanf("%d%d",&row,&col); //終點坐標
t=row*n+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
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX