C++广度优先搜索

简介

老规矩，先来介绍一下什么是广度优先搜索（至于这么长时间没更新是为什么，我放在文章结尾了，感兴趣可以看看，以后也是如此）

广度优先搜索，从名字就能听出来，他和深度优先搜索关系匪浅，没错，他们是“孪生兄弟”。两者虽然是“孪生兄弟”但差别可是巨大无比：一个会深入每一条路径，也就是“不撞南墙不回头”；而另一个则侧重于搜索的广泛性。这么说吧一个是线性的搜索，另一个是面性的搜索。

接下来就是详细的解释了

广度优先搜索，以一个点为中心，不断向周围探索，先探索中心点的周围四个格子，再将中心按顺序转为一个个新的格子，再向自己的周围探索......就这样循环，向周围扩散式探索；比如指定A为中心点，先探索A四周的格子，依次为B、C、D、E。完成后再将中心点转为B，继续探索B的四周（探索过的除外）为1、2、3。再转为C，探索四周，转为D，探索四周，转为E，探索四周，再继续转为1，探索四周......2......3......这样循环下去，不理解的可以自己动手画个图，会对理解有帮助。

正文开始

迷宫出口

题目描述 ：一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以 看成是由 n×n 的格点组成，每个格点只有 2 种状态， 0 和 1，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点 A 走到点 B ， 问在不走出迷宫的情况下能不能办到。 如果起点或者终点有一个不能通行(为 11)，则看成无法办到。

输入 第 1 行是一个正整数 n (1≤n≤100)，表示迷宫的规模是 n×n 的。 接下来是一个 n×n 的矩阵，矩阵中的元素为 0 或者 1。 再接下来一行是 4 个整数 表示入口和出口的坐标。 输出： 能办到则输出 YES，否则输出 NO。

样例

输入复制

3

0 1 1

0 0 1

1 0 0

1 1 3 3

输出复制

YES

#include<bits/stdc++.h>
using namespace std;
int a[110][110]={0};
int x[110]={0};
int y[110]={0};
int n=0;
int q=0,p=0;
int s1,s2,e1,e2;
bool jian_ce(int,int);
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}cin>>s1>>s2>>e1>>e2;s1--;s2--;e1--;e2--;q++;x[q]=1;y[q]=1;p++;while(true){if(a[x[p]+1][y[p]]!=1&&x[p]+1<n){q++;x[q]=x[q-1]+1;y[q]=y[q-1];if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]][y[p]+1]!=1&&y[p]+1<n){q++;x[q]=x[q];y[q]=y[q]+1;if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]-1][y[p]]!=1&&x[p]-1>=0){q++;x[q]=x[q]-1;y[q]=y[q];if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]][y[p]-1]!=1&&y[p]-1>=0){q++;x[q]=x[q];y[q]=y[q]-1;if(jian_ce(x[q],y[q])==true)return 0;}p++;}cout<<"NO";return 0;
}
bool jian_ce(int t1,int t2)
{if(t1==e1&&t2==e2){cout<<"YES";return true;}return false;
}

至于为什么没更新，因为.........懒得q(≧▽≦q)