采用双向搜索,如何知道某个结点是正向还是逆向扩展来的呢?
简单修改vis[][]数组元素的置值方法即可。初始时,vis数组的全部元素值为0,由正向扩展来的结点的vis对应元素值置为1,由逆向扩展来的结点的vis对应元素值置为2。
设当前结点为cur,由cur可以扩展出新结点next。若vis[next.x][next.y]==0,则next结点未访问过,将next结点入队并进行相应设置;若vis[next.x][next.y]!=0,则next结点已访问过。由于vis[cur.x][cur.y]记录的是当前扩展方向(1代表正向,2代表逆向),若vis[next.x][next.y] != vis[cur.x][cur.y],则表示next结点以前按相反的方向访问过,正向和反向遇到了同一个结点,搜索成功。
(4)采用双向广度优先搜索的源程序。
#include <stdio.h>
int vis[305][305], step[305][305];
int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
struct point
{
int x, y;
};
int BFS(int start_x,int start_y,int end_x,int end_y,int n)
// 在n*n的棋盘中搜索从起点(start_x,strat_y)到终点(end_x,end_y)所需的最少步数
{
int front,rear,i;
point cur,next,q[90005];
front=rear=0;
cur.x = start_x;
cur.y = start_y;
vis[start_x][start_y] = 1; // 从起始位置开始的探索标记为1
q[rear++] = cur; // 起始坐标入队
next.x = end_x;
next.y = end_y;
vis[end_x][end_y] = 2; // 从终点位置开始的探索标记为 2
q[rear++] = next; // 终点坐标入队
while (front < rear)
{
cur = q[front++]; /* 队首结点坐标出队 */
for (i=0; i<8; ++i)
{
next.x = cur.x + dx[i];
next.y = cur.y + dy[i];
if (next.x<0 || next.x>=n || next.y<0 || next.y>=n)
continue;
if (!vis[next.x][next.y])
{
vis[next.x][next.y] = vis[cur.x][cur.y]; // 设为与当前探索路径相同的标记
step[next.x][next.y] = step[cur.x][cur.y] + 1; // 记录步数
q[rear++] = next; // 当前合法坐标位置入队
}
else if (vis[cur.x][cur.y] != vis[next.x][next.y])
{ // 说明从起点出发的探索与从终点出发的探索重合
&nbs