深度优先搜索的本质是递归，广度优先搜索不需要递归
深度优先搜索不要用栈实现，广度优先搜索要用队列实现
scanf()按s格式符不能输入带空格的字符串
gets()能输入带空格的字符串
【算法笔记-广度优先搜索】scanf()以回车符作为字符串的终止符，同时不读走回车符，回车符仍然留在输入缓冲区中
gets()以回车符作为字符串的终止符，同时将回车符从输入缓冲区读走，但不作为字符串的一部分
《C语言程序设计（苏小红）》P258
当需要读入字符时，可以套用以下代码：
scanf("%d%d"，&n,&m);
for(int i=0;
igetchar()的作用是从系统隐含指定的输入设备（即终端键盘）输入一个字符，按回车键表示输入结束，也接受空格
下面举一个迷宫的例子，输入一个迷宫，输入起点终点，通过广度优先搜索得到最短路径：
#include
#include
#include
#include
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 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 
文章图片
广度优先搜索适合求最短路径，因为只要第一次发现满足条件的路径，该路径一定是最短路径，比如上图的迷宫
queue中，元素入队的push操作只是制造了该元素的一个副本入队，因此在入队后对原元素的修改不会改变队列中的副本，而对队列中副本的修改也不会改变原元素，需要注意由此可能引入的bug
当需要对队列queue中的元素进行修改而不仅仅是访问时，队列中存放的元素最好不要是元素本身，而是它们的编号 （如果是数组的话则是下标）
