广搜的定义在此不再赘述，特别的，它非常适宜于解决“最少”这种发问的问题，一般由队列实现，我在锻炼的过程中也有了一些感悟。
首先广搜的问题是由迷宫问题引出的，这里设置两个增量数组比较简洁，从这里开始我就注意到广搜的分支其实比较容易写，关键在于这些数据如何存储和如何判重，解决了这两个，可能问题就比较清晰，下面是一些实例。
引、矩阵找块
题目： 求01矩阵中,一个位置上下左右是为相邻，若若干个1相邻，它们就构成了一个块，求块的个数
分析：这个题目其实用bfs和dfs均可以，其实和数据学图后找连通分量差不多。遍历矩阵所有点，如果遇到1采用bfs把这一块全部遍历，块数加一，注意遍历后应该标记以判重，这里由于矩阵不大，直接用两个二重数组存储矩阵和状态。
#include<iostream> #include<queue> using namespace std; int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; int a[15][15],count=0,n,m; bool b[15][15]; struct node{ int x,y; }; node t,temp; void bfs(node start){ //进入这个点为1点 ，广搜法 queue<node> q; q.push(start); while(!q.empty()){ t=q.front();q.pop(); for(int i=0;i<4;i++) { if(a[t.x+dx[i]][t.y+dy[i]]&&1<=t.x+dx[i]&&t.x+dx[i] <=m&&1<=t.y+dy[i]&&t.y+dy[i]<=n&&!b[t.x+dx[i]][t.y+dy[i]]) { b[t.x+dx[i]][t.y+dy[i]]=1; temp.x=t.x+dx[i]; temp.y=t.y+dy[i]; q.push(temp); } } } count++; } void judge(){ for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) if(!b[i][j]&&a[i][j]){ t.x=i;t.y=j; bfs(t); } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); judge(); printf("%d",count); }
入门、8数码难题
题目： 初始状态的步数就算1，哈哈
输入：第一个33的矩阵是原始状态，第二个33的矩阵是目标状态。
输出：移动所用最少的步数
Input
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
Output
6
分析：题目问最少，显然bfs，这里如果用3*3的数组来表示每个状态，再入队出队可能比较占空间，实际上可以将每个状态转化为一个整数即可，再问如何判重?
1.想前面那样开个大数组空间可能不够，但是如果考虑到每个数只出现一次， 开两个9！大小的数组就够了，排好序后再二分查找下标，在另一个数组里判重
2.用map状态与步数一一对应
3.hash
这里其实看了大佬的7种方法思路，最终采用的是map+bfs解决
#include<iostream> #include<queue> #include<algorithm> #include<map> using namespace std; map<int,int>s; int end=0; int x, y; int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; int a[4][4],b[4][4]; int change(){ //对状态进行转化 数组转数组 int sum=0; for(int i=1;i<4;i++) for(int j=1;j<4;j++) sum=sum*10+a[i][j]; return sum; } void zhuanhua(int num)// 数字转数组 { for(int i=3;i>0;i--) for(int j=3;j>0;j--) { a[i][j]=num%10; num=num/10; } } void bfs() { queue<int>q; int temp=change(); s[temp]=1; if(temp==end){ return; } q.push(temp); while(!q.empty()){ temp=q.front();q.pop(); zhuanhua(temp); for(int i=1;i<4;i++) for(int j=1;j<4;j++) { if(a[i][j]==0) { x=i;y=j; } } for(int i=0;i<4;i++) { if(1<=x+dx[i]&&x+dx[i]<=3&&1<=y+dy[i]&&y+dy[i]<=3) { swap(a[x][y],a[x+dx[i]][y+dy[i]]); if(change()==end){ s[change()]=s[temp]+1; return; } if(!s[change()]){ q.push(change()); s[change()]=s[temp]+1; } swap(a[x][y],a[x+dx[i]][y+dy[i]]); } } } } int main(){ for(int i=1;i<4;i++) for(int j=1;j<4;j++) scanf("%d",&a[i][j]); for(int i=1;i<4;i++) for(int j=1;j<4;j++) scanf("%d",&b[i][j]); for(int i=1;i<4;i++) for(int j=1;j<4;j++) end=end*10+b[i][j]; bfs(); printf("%d",s[end]); }
这题反思比较多，无论是全排列+二分+bfs还是map+bfs，都将前面的知识给串起来了，对应这种压缩状态存储的理解也更深了一些。
这里可以开个结构体，0这个点的位置入栈，可以会省一些时间，由于我在Dev上通过了结果如下，而在codeup上编译错误我不太清楚错在哪里就没有细究：
之后我又做了一些题目，如魔块问题用把记录状态的数据就放在结点里，并用字符串储存过程，也有所收获。
