BFS.rar_Bfs算法_bfs_广度优先_广度搜索算法_搜索算法

///////////////////////////////////////////////////////////////////////////////// // // FileName : BFS.cpp // Creater : SZQ // Date : 2011-5-1 // Comment : 广度优先搜索 // ///////////////////////////////////////////////////////////////////////////////// #define MAXN #define DIRNUM 4 // 默认4个方向 int n, m; // n*m的区域 int myQueue[MAXN*MAXN]; // 队列 bool vis[MAXN][MAXN]; // visit， 访问标记数组（需初始化） bool maze[MAXN][MAXN]; // 地图 int dir[MAXN*MAXN]; // PrintPath()内，用于保存递归得到的方向 int lastDir[MAXN][MAXN]; // 从前一个点到当前点的方向 int fa[MAXN][MAXN]; // 当前点的前一个位置 int dist[MAXN][MAXN]; // 当前点与起点的距离 int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; // 控制方向，↑→↓← /** * @param x 当前点横坐标 * @param y 当前点纵坐标 * @return None * @mark 注意初始化数组 */ void BFS(int x, int y) { int front, rear, d, u; /// front, rear：首尾指针；u：编号（0...u...） u = x * m + y; front = rear = 0; vis[x][y] = 1; fa[x][y] = u; /// father, 记录刚走过的点 dist[x][y] = 0; /// distance, 当前点与起点的距离 myQueue[rear++] = u; while (front < rear) { u = myQueue[front++]; x = u / m; y = u % m; /// (x, y): 当前位置 for (d = 0; d < DIRNUM; d++) { int nx = x + dx[d]; int ny = y + dy[d]; /// 新生点 if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] /// 标记当前格子是否可走 && !vis[nx][ny]) { int v = nx * m + ny; myQueue[rear++] = v; vis[nx][ny] = 1; fa[nx][ny] = u; dist[nx][ny] = dis[x][y] + 1; lastDir[nx][ny] = d;/// 到达当前位置是父位置走的方向 } } } } /** * @brief 保存方向标记 * @param x 当前点横坐标 * @param y 当前点纵坐标 * @return None */ void PrintPath(int x, int y) { int c = 0; for (;;) { int fx = fa[x][y] / m; int fy = fa[x][y] % m; if (fx == x && fy == y) { break; } dir[c++] = lastDir[x][y]; x = fx; y = fy; } while (c--) { putchar(name[dir[c]]); } } /* Description 定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 Input 一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。 Output 左上角到右下角的最短路径，格式如样例所示。 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) #define MAXN 5 int n, m; int Q[MAXN*MAXN]; bool vis[MAXN][MAXN]; bool maze[MAXN][MAXN]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int dir[MAXN*MAXN]; int lastDir[MAXN][MAXN]; int fa[MAXN][MAXN]; //int dist[MAXN][MAXN]; void BFS(int x, int y); void PrintPath(int x, int y); int main() { n = m = 5; memset(maze, 0, sizeof(maze)); memset(vis, 0, sizeof(vis)); memset(dir, 0, sizeof(dir)); memset(lastDir, 0, sizeof(lastDir)); memset(fa, 0, sizeof(fa)); // memset(dist, 0, sizeof(dist)); for (int r = 0; r < n; r++) { for (int c = 0; c < m; c++) { scanf("%d", &maze[r][c]); } } BFS(0, 0); PrintPath(4, 4); } void BFS(int x, int y) { int front, rear, d, u; front = rear = 0; u = x * m + y; vis[x][y] = 1; fa[x][y] = u; // dist[x][y] = 0; Q[rear++] = u; while (front < rear) { u = Q[front++]; x = u / m; y = u % m; for (d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (0 <= nx && nx < n && 0 <= ny && ny < m && !maze[nx][ny] && !vis[nx][ny]) { int v = nx * m + ny; Q[rear++] = v; vis[nx][ny] = 1; fa[nx][ny] = u; // dist[nx][ny] = dist[x][y] + 1; lastDir[nx][ny] = d; } } } } void PrintPath(int x, int y) { int c = 0; for (;;) { int fx = fa[x][y] / m; int fy = fa[x][y] % m; if (fx == x && fy == y) { break; } dir[c++] = lastDir[x][y]; x = fx; y = fy; } x = y = 0; printf("(%d, %d)\n", x, y); while (c--) { printf("(%d, %d)\n", x += dx[dir[c]], y += dy[dir[c]]); } } */