第二讲 搜索
2.1 Flood Fill
2.1.1 1097. 池塘计数
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; char g[N][N]; bool inq[N][N]={false}; int X[8]={0,0,1,-1,-1,1,-1,1}; int Y[8]={1,-1,0,0,1,1,-1,-1}; struct Node{ int x,y; }node; bool judge(int x,int y) { if(x>=n||x<0||y>=m||y<0) { return false; } if(g[x][y]=='.'||inq[x][y]==true) { return false; } return true; } void bfs(int x,int y) { queue<Node> q; node.x=x,node.y=y; q.push(node); inq[x][y]=true; while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<8;i++) { int newX=top.x+X[i]; int newY=top.y+Y[i]; if(judge(newX,newY)) { node.x=newX,node.y=newY; q.push(node); inq[newX][newY]=true; } } } } int main() { cin>>n>>m; getchar(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { char c=getchar(); g[i][j]=c; } getchar(); } int ans=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='W'&&inq[i][j]==false) { ans++; bfs(i,j); } } } cout<<ans; return 0; }
2.1.2 1098. 城堡问题
代码：
#include<bits/stdc++.h> using namespace std; const int N=60; int m,n; int g[N][N][5]; bool inq[N][N]; int X[]={0,-1,0,1},Y[]={-1,0,1,0}; map<int,int> mp; struct Node{ int x,y; }node; void init() { mp[0]=3; mp[1]=4; mp[2]=1; mp[3]=2; } int judge(int x,int y,int flag) { if(x>=m||x<0||y>=n||y<0) { return false; } if(g[x][y][flag]==1||inq[x][y]==true) { return false; } return true; } int bfs(int x,int y) { int ans=1; queue<Node> q; node.x=x,node.y=y; q.push(node); inq[x][y]=true; while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<4;i++) { int newX=top.x+X[i]; int newY=top.y+Y[i]; if(judge(newX,newY,mp[i])) { node.x=newX,node.y=newY; q.push(node); inq[newX][newY]=true; ans++; } } } return ans; } int main() { cin>>m>>n; init(); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { int x; cin>>x; g[i][j][1]=x&1; g[i][j][2]=(x&2)>>1; g[i][j][3]=(x&4)>>2; g[i][j][4]=(x&8)>>3; } } int ans=0,s=0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(inq[i][j]==false) { ans++; s=max(s,bfs(i,j)); } } } cout<<ans<<endl<<s; return 0; }
2.1.3 1106. 山峰和山谷
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010; int n; int g[N][N]; bool inq[N][N]; int X[]={0,0,1,-1,-1,-1,1,1},Y[]={1,-1,0,0,-1,1,-1,1}; struct Node{ int x,y; }node; bool judge(int x,int y,int sx,int sy) { if(x>=n||x<0||y>=n||y<0) { return false; } if(g[x][y]!=g[sx][sy]||inq[x][y]==true) { return false; } return true; } int bfs(int x,int y) { queue<Node> q,sv; node.x=x,node.y=y; q.push(node); inq[x][y]=true; sv.push(node); while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<8;i++) { int newX=top.x+X[i],newY=top.y+Y[i]; if(judge(newX,newY,x,y)) { node.x=newX,node.y=newY; q.push(node); inq[newX][newY]=true; sv.push(node); } } } int h=0,l=0; bool flagh=true,flagl=true; while(!sv.empty()) { Node top=sv.front(); sv.pop(); for(int i=0;i<8;i++) { int newX=top.x+X[i],newY=top.y+Y[i]; if(!(newX>=n||newX<0||newY>=n||newY<0)) { if(g[x][y]<g[newX][newY]) { flagh=false; } if(g[x][y]>g[newX][newY]) { flagl=false; } } } } if(flagh&&flagl) { return 2; } if(flagh) { return 1; } if(flagl) { return -1; } return 0; } int main() { ios::sync_with_stdio(0); cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>g[i][j]; } } int h=0,l=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(inq[i][j]==false) { int x=bfs(i,j); if(x==2) { h++; l++; } else if(x==1) h++; else if(x==-1) l++; } } } cout<<h<<" "<<l; return 0; }
2.2 最短路模型
2.2.1 1076. 迷宫问题
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010; int n; int g[N][N]; bool inq[N][N]; struct Node{ int x,y; }node; Node pre[N][N]; int X[]={0,0,1,-1},Y[]={1,-1,0,0}; bool judge(int x,int y) { if(x>=n||x<0||y>=n||y<0) return false; if(g[x][y]==1||inq[x][y]==true) return false; return true; } void bfs(int x,int y) { queue<Node> q; node.x=x,node.y=y; q.push(node); inq[x][y]=true; while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<4;i++) { int newX=top.x+X[i],newY=top.y+Y[i]; if(judge(newX,newY)) { node.x=newX,node.y=newY; q.push(node); node.x=top.x,node.y=top.y; pre[newX][newY]=node; inq[newX][newY]=true; } } } } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>g[i][j]; } } bfs(n-1,n-1); node.x=0,node.y=0; while(true) { cout<<node.x<<" "<<node.y<<endl; if(node.x==n-1&&node.y==n-1) break; node=pre[node.x][node.y]; } return 0; }
2.2.2 188. 武士风度的牛
代码：
#include<bits/stdc++.h> using namespace std; const int N=160; int r,c; int g[N][N]; bool inq[N][N]; int sx,sy,ex,ey; int X[]={-2,-2,-1,-1,1,1,2,2}; int Y[]={-1,1,-2,2,2,-2,1,-1}; int dist[N][N]; struct Node{ int x,y; }node; bool judge(int x,int y) { if(x>=r||x<0||y>=c||y<0) return false; if(g[x][y]=='*'||inq[x][y]==true) return false; return true; } int bfs(int x,int y) { queue<Node> q; node.x=x,node.y=y; q.push(node); inq[x][y]=true; while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<8;i++) { int newX=top.x+X[i],newY=top.y+Y[i]; if(judge(newX,newY)) { node.x=newX,node.y=newY; dist[newX][newY]=dist[top.x][top.y]+1; q.push(node); inq[newX][newY]=true; } } } return dist[ex][ey]; } int main() { cin>>c>>r; getchar(); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { char ch=getchar(); if(ch=='K') { sx=i,sy=j; } if(ch=='H') { ex=i,ey=j; } g[i][j]=ch; } getchar(); } cout<<bfs(sx,sy); return 0; }
2.2.3 1100. 抓住那头牛
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010; int n,k; bool inq[N]; int dist[2*N]; int getX(int x,int flag) { if(flag==0) x=2*x; else if(flag==1) x-=1; else x+=1; return x; } void bfs(int x) { queue<int> q; q.push(x); inq[x]=true; dist[x]=0; while(!q.empty()) { int top=q.front(); q.pop(); for(int i=0;i<3;i++) { int newX=getX(top,i); if(newX>=0&&newX<N&&inq[newX]==false) { q.push(newX); inq[newX]=true; dist[newX]=min(dist[newX],dist[top]+1); } } } } int main() { cin>>n>>k; fill(dist,dist+2*N,1e9); bfs(n); cout<<dist[k]; return 0; }
2.3 多源BFS
2.3.1 173. 矩阵距离
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; int g[N][N]; int dist[N][N]; int X[]={0,0,1,-1},Y[]={1,-1,0,0}; struct Node{ int x,y; }node; bool judge(int x,int y) { if(x>=n||x<0||y>=m||y<0) return false; if(g[x][y]=='1'||dist[x][y]!=-1) return false; return true; } void bfs() { fill(dist[0],dist[0]+N*N,-1); queue<Node> q; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='1') { node.x=i,node.y=j; dist[i][j]=0; q.push(node); } } } while(!q.empty()) { Node top=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=top.x+X[i],y=top.y+Y[i]; if(judge(x,y)) { node.x=x,node.y=y; q.push(node); dist[x][y]=dist[top.x][top.y]+1; } } } } int main() { cin>>n>>m; getchar(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { g[i][j]=getchar(); } getchar(); } bfs(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cout<<dist[i][j]<<" "; } cout<<endl; } return 0; }
