BFS及其优化
BFS可实现问题:
[连通块]
(DFS也行)
[最短路]
(DFS又行)
[曼哈顿距离]
(DFS好像大概也许行)
大概步骤:
1.起点入队列，打标记。
2.弹出队首进行操作。
3.按照题目要求加入队列新点并打标记。
例题:
1.
accoders【一本通提高篇广搜的优化技巧】山峰和山谷2065
思路:
运用BFS模版查连通块，有比当前高的就把g记打上，有比当前矮的就把f打上，
结束后若g=0山谷++,若f=0山峰++。
注:高低判断需要放在走过标记判断前。
code:
#include<bits/stdc++.h>
using namespace std;
int dx[9]={0,-1,-1,-1,0,1,1,1,0},dy[9]={0,-1,0,1,1,1,0,-1,-1};
int n,mp[1010][1010],h,l,hh,tt;
int vis[1010][1010];
struct node{
int x,y;
}q[1010*1010];
void bfs(int sx,int sy){
hh=1,tt=0;
q[++tt]={sx,sy};
vis[sx][sy]=1;
while(hh<=tt){
int x=q[hh].x,y=q[hh++].y;
for(int i=1;i<=8;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<=n&&xx>=1&&yy<=n&&yy>=1){
if(mp[xx][yy]>mp[x][y]){
h=1;
}else if(mp[xx][yy]<mp[x][y]){
l=1;
}else if(mp[xx][yy]==mp[x][y]&&!vis[xx][yy]){
q[++tt]={xx,yy};
vis[xx][yy]=1;
}
}
}
}
return ;
}
int main(){
int f,g;
f=g=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j]){
continue;
}
h=l=0;
bfs(i,j);
if(!h){
f++;
}
if(!l){
g++;
}
}
}
cout<<f<<" "<<g;
return 0;
}
2.
accoders的武士风度的牛
思路:
(其实就是马走日(划掉))
用a数组用来计算走过的步数，最开始除起点外设为inf，
之后每到一个就更新一次a[xx][yy]=min(a[xx][yy],a[x][y]+1)。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[201][201],a[201][201],hh,tt,dx[9]={0,2,2,-2,-2,1,1,-1,-1},dy[9]={0,1,-1,1,-1,2,-2,2,-2};
char mp[201][201];
struct node{
int x,y;
}q[200*200];
void bfs(int sx,int sy){
hh=1,tt=0;
vis[sx][sy]=1;
q[++tt]={sx,sy};
while(hh<=tt){
int x=q[hh].x,y=q[hh++].y;
if(mp[x][y]=='H'){
cout<<a[x][y];
return ;
}
for(int i=1;i<=8;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>0&&xx<=n&&yy>0&&yy<=m&&!vis[xx][yy]&&mp[xx][yy]!='*'){
q[++tt]={xx,yy};
a[xx][yy]=min(a[xx][yy],a[x][y]+1);
vis[xx][yy]=1;
}
}
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
memset(a,0x3f3f3f,sizeof a);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='K'){
vis[i][j]=1;
a[i][j]=0;
bfs(i,j);
}
}
}
return 0;
}
3.
accoders的【一本通基础广度优先搜索】迷宫问题 1912
思路:
简单的BFS，极其恶心的输出方式。
cond:
#include<bits/stdc++.h>
using namespace std;
int mp[10][10],vis[10][10],tt,hh,a[10][10];
int n;
struct node{
int x,y;
}q[11*11],st[10][10],ans[10*10];
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
void bfs(int sx,int sy){
hh=1,tt=0;
q[++tt]={sx,sy};
vis[sx][sy]=1;
while(hh<=tt){
int x=q[hh].x,y=q[hh++].y;
for(int i=1;i<=4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>0&&xx<=n&&yy>0&&yy<=n&&!vis[xx][yy]&&mp[xx][yy]==0){
q[++tt]={xx,yy};
vis[xx][yy]=1;
if(a[xx][yy]>a[x][y]+1){
st[xx][yy]={x-1,y-1};
a[xx][yy]=a[x][y]+1;
}
}
}
}
return ;
}
int main(){
//cin>>n;
n=5;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
memset(a,0x3f3f3f,sizeof a);
vis[1][1]=1;
a[1][1]=0;
bfs(1,1);
int fx=5,fy=5,cnt=0;
ans[++cnt]={fx-1,fy-1};
while(1){
//cout<<fx<<" "<<fy<<" "<<st[fx][fy].x<<" "<<st[fx][fy].y<<"\n";
ans[++cnt]={st[fx][fy].x,st[fx][fy].y};
int xxx=fx;
fx=st[fx][fy].x+1;
fy=st[xxx][fy].y+1;
if(st[fx][fy].x==0&&st[fx][fy].y==0){
break;
}
}
ans[++cnt]={0,0};
for(int i=cnt;i>=1;i--){
cout<<"("<<ans[i].x<<", "<<ans[i].y<<")"<<"\n";
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<"("<<st[i][j].x<<", "<<st[i][j].y<<")"<<"";
// }
// cout<<"\n";
// }
return 0;
}
4.
accoders的【算法进阶 搜索广度优先搜索】矩阵距离2520
思路:
逆向思考，从所有1出发向0进行BFS，记录步数输出。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
struct node{
int x,y;
}q[1005*1005];
int tt=0,hh=1,vis[1010][1010],a[1010][1010];
char mp[1010][1010];
void bfs(){
while(hh<=tt){
int x=q[hh].x,y=q[hh++].y;
for(int i=1;i<=4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>0&&xx<=n&&yy>0&&yy<=m&&!vis[xx][yy]){
q[++tt]={xx,yy};
vis[xx][yy]=1;
a[xx][yy]=a[x][y]+1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='1'){
q[++tt]={i,j};
vis[i][j]=1;
}
}
}
bfs();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
5.
accoders【一本通提高篇广搜的优化技巧】 魔板
luogu P2730 [USACO3.2] 魔板 Magic Squares
code:
#include<bits/stdc++.h>
using namespace std;
const int ten[10]={1,10,100,1000,10000,100000,1000000,10000000};
struct node{
int key,st,pr,wa;
}l[1000050];
unordered_map<int,int> vis;
int A(int x){
return x/10000+x%10000*10000;
}
int B(int x){
int ll=x/10000,rr=x%10000;
ll=ll/10+ll%10*1000;
rr=rr/10+rr%10*1000;
return ll*10000+rr;
}
int C(int x){
int a=x/ten[7]%10;
int b=x/ten[6]%10;
int c=x/ten[5]%10;
int d=x/ten[4]%10;
int e=x/ten[3]%10;
int f=x/ten[2]%10;
int g=x/ten[1]%10;
int h=x/ten[0]%10;
return a*ten[7]+f*ten[6]+b*ten[5]+d*ten[4]+e*ten[3]+g*ten[2]+c*ten[1]+h*ten[0];
}
void show(int id){
if(l[id].pr==-1){
return ;
}
show(l[id].pr);
putchar(l[id].wa);
}
void bfs(int sx,int fx){
int hh=1,tt=0;
vis[sx]=1049;
l[++tt]={sx,0,-1,-1};
while(hh<=tt){
int ke=l[hh].key,pr=hh,st=l[hh++].st+1;
int a=A(ke),b=B(ke),c=C(ke);
if(vis[a]!=1049){
vis[a]=1049;
l[++tt]={a,st,pr,(int)'A'};
if(a==fx){
printf("%d\n",st);
show(tt);
return;
}
}
if(vis[b]!=1049){
vis[b]=1049;
l[++tt]={b,st,pr,(int)'B'};
if(b==fx){
printf("%d\n",st);
show(tt);
return;
}
}
if(vis[c]!=1049){
vis[c]=1049;
l[++tt]={c,st,pr,(int)'C'};
if(c==fx){
printf("%d\n",st);
show(tt);
return ;
}
}
}
}
int main(){
vis.clear();
int l1[6],l2[6],k=0;
for(int i=1;i<=4;i++){
scanf("%d",&l1[i]);
}
for(int i=1;i<=4;i++){
scanf("%d",&l2[i]);
}
for(int i=1;i<=4;i++){
k=k*10+l1[i];
}
for(int i=4;i>=1;i--){
k=k*10+l2[i];
}
if(k==12348765){
cout<<0<<"\n";
return 0;
}
bfs(12348765,k);
return 0;
}
6.
accoders【一本通提高篇广搜的优化技巧】电路维修
luogu P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修
luogu须把while删了
code:
#include<bits/stdc++.h>
using namespace std;
char mp[510][510];
int vis[510][510],a[510][510];
int n,m,tt,hh;
int dx1[]={0,-1,-1,1,1},dy1[]={0,-1,1,1,-1};//顶点与顶点
int dx2[]={0,-1,-1,0,0},dy2[]={0,-1,0,0,-1};//顶点与方格
struct node{
int x,y;
};
int bfs(int sx,int sy){
char c[]="-\\/\\/";
deque<node> q;
memset(a,0x3f,sizeof a);
a[sx][sy]=0;
q.push_front({sx,sy});
while(!q.empty()){
node t=q.front();
q.pop_front();
int x=t.x,y=t.y;
if(x==n&&y==m)return a[x][y];
if(vis[x][y])continue;
vis[x][y]=1;
//printf("%d,%d %d needed!\n",x,y,a[x][y]);
for(int i=1;i<=4;i++){
int xx1=x+dx1[i],yy1=y+dy1[i];
if(xx1>=0&&xx1<=n&&yy1>=0&&yy1<=m){
int xx2=x+dx2[i],yy2=y+dy2[i];
int w=(mp[xx2][yy2]!=c[i]);
if(a[xx1][yy1]>=a[x][y]+w){
a[xx1][yy1]=a[x][y]+w;
if(w){
q.push_back({xx1,yy1});
}else{
q.push_front({xx1,yy1});
}
}
}
}
}
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
memset(vis,0,sizeof vis);
for(int i=0;i<n;i++){
cin>>mp[i];
}
if((n+m)%2==1){
cout<<"NO SOLUTION"<<"\n";
}else if(n+m==0){
cout<<0<<"\n";
}else{
cout<<bfs(0,0)<<"\n";
}
}
return 0;
}