1. Floodfill
给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。 提示：参考第2题。 2. 电子老鼠闯迷宫
如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。
本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下： #include
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(\ //打印结果 }
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(\ 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(\ scanf(\ //起点坐标 s=row*n+col; scanf(\ //终点坐标 t=row*n+col; gets(str); for(i=0;i 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 注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。 想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。 3. 跳马 给一个200×200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。 Sample Input 0 0 1 1 Sample output 4 状态：马所在的行、列。 程序如下： #include void readdata(); //读入数据 void init(); //初始化 int search(); //广度优先搜索 int emptyopen(); //判栈是否为空：空：1；非空：0。 long 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[200][200],n=200; //a存放棋盘，n为迷宫边长 long open[2000],head,tail,openlen=2000; //open表1367 long s,t; //起点和终点 int search() { long u; int row, col, r, c, i, num; while(!emptyopen()) //当栈非空 { u=takeoutofopen(); //从栈中取出一个元素，并把该元素从栈中删除 row=u/n; //计算该点所在的行 col=u%n; //计算该点所在的列 num=a[row][col]; //取得该点的步数 for(i=0;i<8;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表 } } } } return -1; }