算法设计与分析实验报告3

《算法设计与分析实验报告3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、武汉zOAf计算机科学与工程学院《算法设计与分析》实验报告专业班级实验地点学生学号指导教师张立学生姓名实验时间实验项目图的搜索算法实验类别设计性实验实验目的及要求目的与要求：练习图的搜索算法的使用实验内容要点：1、熟悉广度优先搜索算法以及深度优先搜索算法的应用2、掌握冋溯法和分支限界法的应用成绩评定表类另IJ评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成实验设计任务30分实验报告及时递交、填写规范内容完整、体现收获70分说明：评阅教师：日期：年月日实验内容1、走迷宫问题。迷宫是许多小方格构成的矩形，如图3-3所示，在每个小方格中有的是墙（图中的“1”）有的是路（图中的“0”）。走迷宫

2、就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口在左上角（1,1）,出口是右下角（8,8）o根据给定的迷宫，找出一条入口到出口的路径。0000000001111010000010100100001001011010010000110100100001111110图3-1迷宫矩形图#includeintmaze[8][8]={{0,0,0,0,0,0,0,0},{0,1,1,1,1,0,1,0},{0,0,0,0丄0丄0},{0,1,0,0,0,0,1,0},{0,1,0,14,0,1,0},{0,1,0,0,0,0,1,1},{0,1,

3、0,0,1,0,0,0},{0,1,1,1,1,1,1,0}};intfx[4]={1,-1,0,0},fy[4]={0,0,-1,1};struct}intx,y,pre;}sq[100];intqh,qe,i,j,k;intcheck(inti,intj);intsearch();voidout();voidmain(){search();}intsearch(){qh=O;qe=l;maze[0][0]=-l;sq[O].pre=O;sq[0].x=0;sq[O].y=O;while(qh!=qe)qh=qh+l;for(k=0;k<=3;k++)i=sq[qh].x+fx[k];j=

4、sq[qh].y+fy[k];if(check(i,j)==l){qe二qe+1;sq[qe].x=i;sq[qe].y=j;sq[qe]

5、

6、i>7

7、[j<0

8、U>7)flag=0;if(maze[i][j]==l

9、

10、maze[i][j]==-l)flag=0;return(flag);}voidout(){cout«n(n«sq[qe].x«,,,,

11、,«sq[qe].y«n)"«endl;while(sq[qe].pre!=0)qe=sq[qe].pre;cout«H-,,«,,("«sq[qe].x«,,；,«sq[qe].y«,,),f«endl;亍wE:VCllllDebuglllLexe,i〔口

12、回

13、■牛g

14、—<6,7〉—〉一一<6.5〉一一<5.5〉一一匕4〉一一03〉--<5,2〉一一<4,2〉一一<3.2〉―<2,2>一一C2.1〉—<2,0>―<1,0>—<0,0>Pressanykeytocontinue.图3~22、有如图3-3所示的七巧板，试设计算法，使用至多4种不同颜色对七巧板进行涂色（每块涂一

15、种颜色），要求相邻区域的颜色互不和同，打印输出所有可能的涂色方案。#includeintdata[8][8],n=8,color[8],total;voidtrys(ints);intcolorsame(ints);voidoutput();voidmain(){inti,j；for(i=l;i<=7;i++)forG=l;j<=7;j++)scanf(”％d”,&data[i]

16、j]);for(j=l;j<=7;j++)color[j]=0;total=0;trys(l);printf(nTotal=%dn,total);}voidtrys(ints){inti;if

17、(s>7)output();elsefor(i=l;i<=4;i++){color[s]=i;if(colorsame(s)==0)trys(s+l);}}intcolorsame(ints){inti,flag;flag=0;for(i=l;i<=s-l;i++)if(data[i][s]==1&&color[i]==color[s])flag=l;retum(flag);}voidoutput(){int