suanfafenxi.txt

算法设计与分析的实验指导

	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;
}

8．	农场灌溉问题（ZOJ2412）
一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图，编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。
  
Sample Input
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1
Sample Output
2
3
    提示：参考迷宫问题，实现时关键要解决好各块的表示问题。
9．	求图像的周长（ZOJ1047）
给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。
输入：首先给出m、n、x、y四个正整数，下面给出m×n的图形，x、y表示点击的位置，全0表示结束。
输出：点击的图形的周长。
                 
Sample Input
2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...
0 0 0 0 
Sample output
8
18
提示：参考迷宫问题，区别在于它是向8个方向填。

10．	骨牌矩阵
多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0~6），现在有28组骨牌，每组两个，各组编号为1~28，每组编号对应的两个骨牌数值如下：
00  01  02  03  04  05  06
11  12  13  14  15  16  22
23  24  25  26  33  34  35
36  44  45  46  55  56  66
现将这28组骨牌排成一个7×8矩阵，此时只能看到每个骨牌上的数字（0~6），而不能知道每组的组号（如左下图所示）。请编程序将每组骨牌分辨出来（如右下图所示）。
7X8骨牌矩阵        骨牌组编号矩阵
66265241               28  28  14   7  17  17  11  11
13201034               10  10  14   7   2   2  21  23
13246654                8   4  16  25  25  13  21  23
10432112                8   4  16  15  15  13   9   9
51360455               12  12  22  22   5   5  26  26
55402603               27  24  24   3   3  18   1  19
60534203               27   6   6  20  20  18   1  19
void search(int n)
{
    查找下一个还没放置骨牌的位置(x,y);
        若没有，则表示已经找到一个解，输出并且返回；
    尝试放置骨牌； 
    两次尝试都失败，进行回溯；
}
尝试放置骨牌
?	把在(x,y)处的骨牌作为当前骨牌组的一个骨牌；
?	把(x+1,y)处的骨牌作为当前骨牌组的另一个骨牌；
?	判断当前骨牌组是够未被使用，如果未被使用则递归放置下一个骨牌组；
?	把(x,y +1)处的骨牌作为当前骨牌组的另一个骨牌；
?	判断当前骨牌组是否未被使用，如果未被使用则递归放置下一个骨牌组；

11．	字母转换（ZOJ1003）
通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT: 
[
i i i i o o o o
i o i i o o i o
]
Sample Input
madam
adamm
bahama
bahama
long
short
eric
rice
Sample Output
[
i i i i o o o i o o 
i i i i o o o o i o 
i i o i o i o i o o 
i i o i o i o o i o 
]
[
i o i i i o o i i o o o 
i o i i i o o o i o i o 
i o i o i o i i i o o o 
i o i o i o i o i o i o 
]
[
]
[
i i o i o i o o 
]

12．	踩气球（ZOJ1004）
六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。
输入为两个数字，0 0表示结束；
输出为获胜的数字。
Sample Input
36 62
49 343
0 0
Sample Output
62
49
 
实验三：搜索算法
实验目的：熟练掌握搜索算法
实验内容：广度优先搜索
搜索算法的一般模式：
void search()
{
	closed表初始化为空;
	open表初始化为空;
	起点加入到open表;
	while( open表非空 )
	{
		取open表中的一个结点u;
		从open表中删除u;
		u进入closed表;
		for( 对扩展结点u得到的每个新结点vi )
		{
			if(vi是目标结点)
				输出结果并返回;
			if vi 的状态与closed表和open表中的结点的状态都不相同
				vi进入open表;
		}
	}
}
搜索算法关键要解决好状态判重的问题，这样可省略closed表，一般模式可改为：
void search()
{
	open表初始化为空;
	起点加入到open表;
	while( open表非空 )
	{
		取open表中的一个结点u;
		从open表中删除u;
		for( 对扩展结点u得到的每个新结点vi )
		{
			if(vi是目标结点)
				输出结果并返回;
			If(notused(vi))
				vi进入open表;
		}
	}
}
1.	Floodfill
给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。
提示：参考第2题。
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