宽优先搜索新学习资料PPT教案.pptx

会计学
1
宽优先搜索新学****资料
任务：处在（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
第2页/共66页
根据马的跳步规则研究8个方向的跳步增量dx[k],dy[k], k=0,1,…7 6
-2 -1 0 1 2
-2 5
-1
7 0 4
1
2
k = 0 1 2 3
第3页/共66页
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）
第4页/共66页
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] , 3
k=0,1,…7 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
第5页/共66页
定义二维数组
int w[5][5];
用来存储每个格子中马的跳步信息
对数组w进行初始化，目的是让每个格子只记录一次，避免重复记录。
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
w[i][j]=-1;
第6页/共66页
经初始化后的5x5格子中的数字均为-1
0