宽度优先搜索.ppt

声明:声明:本课件版权归本课件版权归清华大学计算机系语音技术中心清华大学计算机系语音技术中心所有所有未经许可未经许可不得扩散不得扩散宽度优先搜索任务:处在(0,0)位置上的象棋马跳到任何一个位置所需步数 0 1 2 3 4 y 0 0 3 2 3 2 1 3 4 1 2 3 2 2 1 4 3 2 3 3 2 3 2 3 4 2 3 2 3 4 x 根据马的跳步规则研究8个方向的跳步增量dx[k],dy[k], k=0,1,…7 6 -2 -1 0 1 2 -2 5 -1 7 0 41 2k =k =0 0 1122 3 3 k 0 1 2 3 4 5 6 7 dx 1 2 2 1 -1 -2 -2 -1 dy -2 -1 1 2 2 1 -1 -2 dx----马跳一步在x方向上的增量 dy----马跳一步在y方向上的增量 k----- 方向号从(x,y)马跳一步到(x1,y1) x1=x+dx[k]; 0 1 2 3 4 y1=y+dy[k]; 0 0 如马的初始位置在(0,0)则 1 1 x1=0+dx[k] 2 1 y1=0+dy[k] , k=0,1…7 3 4 k 0 1 2 3 4 5 6 7 x1 1 2 2 1 -1 -2 -2 -1 y1 -2 -1 1 2 2 1 -1 -2 定义二维数组 int w[5][5]; 用来存储每个格子中马的跳步信息对数组w进行初始化,目的是让每个格子只记录一次,避免重复记录。 for(int i=0;i<=4;i++) for(int j=0;j<=4;j++) w[i][j]=-1; 经初始化后的5x5格子中的数字均为-1 0 1 2 3 4 0 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 下面会看到,格子中的数为-1时才允许存入跳步信息。马从(马从(00,,00)跳一步,有两个可行位置)跳一步,有两个