共计 1638 个字符,预计需要花费 5 分钟才能阅读完成。
深度优先搜寻的实质是 递归 ,广度优先搜寻 不须要递归
深度优先搜寻 不要用栈实现 ,广度优先搜寻 要用队列实现
scanf()按 s 格局符 不能 输出带空格的字符串
gets()能 输出带空格的字符串
scanf()以回车符作为字符串的终止符,同时 不读走 回车符,回车符依然留在输出缓冲区中
gets()以回车符作为字符串的终止符,同时将回车符从输出缓冲区 读走,但不作为字符串的一部分
《C 语言程序设计(苏小红)》P258
当须要读入字符时,能够套用以下代码:
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){getchar();// 过滤掉每行前面的换行符
for(int j=0; j<m; j++){maze[i][j] = getchar();}
maze[i][m+1] = '\0;'
}
getchar()的作用是从零碎隐含指定的输出设施(即终端键盘)输出 一个 字符,按 回车键 示意输出完结,也承受 空格
上面举一个迷宫的例子,输出一个迷宫,输出终点起点,通过广度优先搜寻失去最短门路:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
const int maxn = 1000;
char maze[maxn][maxn];
bool inq[maxn][maxn];
int n;
int m;
struct node
{
int x;
int y;
int step;
};
node S;
node T;
node mid;
int ans=0;
int xChange[4] = {0,0,-1,1};
int yChange[4] = {1,-1,0,0};
queue<node> link;
bool judge(int x,int y)
{if(x<0||x>=m||y<0||y>=n)
{return false;}
if(maze[x][y]=='*' || inq[x][y]==true)
{return false;}
return true;
}
int BFS()
{link.push(S);
inq[S.x][S.y] = true;
while(!link.empty())
{node temp = link.front();
link.pop();
int nowStep = temp.step;
if(temp.x == T.x && temp.y == T.y){
ans = nowStep;
return nowStep;
}
for(int i=0; i<4; i++)
{int tempX = temp.x+xChange[i];
int tempY = temp.y+yChange[i];
if(judge(tempX,tempY)){
node fresh;
fresh.x = tempX;
fresh.y = tempY;
fresh.step = nowStep+1;
link.push(fresh);
inq[tempX][tempY] = true;
}
}
}// 队列齐全可能为空
return -1;
}
int main()
{scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
{getchar();
for(int j=0; j<m; j++)
{maze[i][j] = getchar();}
maze[i][m+1] = '\0';
}
scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
printf("%d", BFS());
return 0;
}
广度优先搜寻适宜求最短门路,因为只有第一次发现满足条件的门路,该门路肯定是最短门路,比方上图的迷宫
queue 中,元素入队的 push 操作只是制作了该元素的一个 正本 入队,因而在入队后对原元素的批改 不会扭转 队列中的正本,而对队列中正本的批改也 不会扭转 原元素,须要留神由此可能引入的 bug
当须要对队列 queue 中的元素进行批改而不仅仅是拜访时,队列中寄存的元素最好不要是元素自身,而是它们的 编号 (如果是数组的话则是 下标)
参考书目:《算法笔记》《C 语言程序设计》
正文完