BFS

一步一步搜索，每层的搜到的点都和起始位置距离相等

基本框架

1. 将初始状态放进队列中

2. while(队列不空){
   取出队头；
   将队头移出队列；

   	进行判断将新的状态放入队列//注意标记
   

   }
   走迷宫

#include
#include 
#includeusing namespace std;const int N=110;
int n,m;
int map[N][N];
int d[N][N];//用于记录步数，同时可以标记哪些点试过了 typedef pair  PII;queue  q;int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};void bfs(){q.push({1,1});//放入初始状态while(!q.empty()){//当q非空 auto t=q.front();//拿出q的第一个元素q.pop();//把队头元素踢出 for(int i=1;i<=4;i++){//遍历所有方向 int x=t.first+dx[i];int y=t.second+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]==0&&d[x][y]==0){d[x][y]=d[t.first][t.second]+1;q.push({x,y});}} 	 } cout<cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>map[i][j];bfs();return 0;
} 

八数码

八数码

将数组转化为字符串存储

代码给了详细的解释

	
#include
#include
#include
#include
#includeusing namespace std;const int N=10;queue  q;
unordered_map  d;int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};string c,s;
string end_s="12345678x";int bfs(){q.push(s);	//将初始状态存入d.insert({s,0}); //记录矩阵状态和对应的距离（这里是初始化） while(!q.empty()){//非空 auto t=q.front();//拿出这个字符串（矩阵） q.pop();//弹出 int distance =d[t];//得到t所需的距离 if (t==end_s)return distance;  //如果到了结尾直接返回值（距离） int k=t.find('x'); //找到x所在的位置int x=k/3,y=k%3;   //根据矩阵和字符串的转化，得到字符串所对应的矩阵中元素的位置 for(int i=1;i<=4;i++){int xx=x+dx[i],yy=y+dy[i];//下一步的位置if(xx>=0&&xx<3&&yy>=0&&yy<3){//如果位置在地图的范围中int m=3*xx+yy;//还原其在字符串中的位置 swap(t[k],t[m]);//将t中x进行一个移动 if(d.count(t)==0){//如果更新后的t没有出现在d中过，就是说我们之前从来没有遍历过q.push(t);d[t]=distance+1;} swap(t[k],t[m]);//还原，用于下一个遍历 } } }		 return -1;//直到空了都没有，就返回-1 }int main(){for(int i=1;i<=9;i++){cin>>c;s+=c;}cout<