1 flood fill
1.Lake Counting
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=115; int n,m,cnt=0; char g[N][N]; bool st[N][N]; pii q[N*N]; void bfs(int sx,int sy) { int hh=0,tt=0; q[0]={sx,sy}; st[sx][sy]=true; while(hh<=tt) { auto t=q[hh++]; for(int i=t.x-1;i<=t.x+1;i++)//因为求八个周围的，则循环枚举两层即可 for(int j=t.y-1;j<=t.y+1;j++) { if(i<0||i>=n||j<0||j>=m) continue;//假如越界则continue if(st[i][j]) continue;//假如标记过则continue if(g[i][j]=='.') continue;//假如是干燥的则continue st[i][j]=true;//标记这个点被标记过 q[++tt]={i,j};//把这个积水放进队列用，以后用他来更新其他的积水 } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) cin>>g[i]; for(int i=0;i<n;i++)//遍历每一个点 for(int j=0;j<m;j++) if(!st[i][j]&&g[i][j]=='W')//假如之前没标记过并且是新的水洼 { bfs(i,j);//遍历这个水洼覆盖的水洼 cnt++;//水洼数量加一 } cout<<cnt<<endl; return 0; }
2.The Castle
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=55; int n,m,cnt=0,ans=0; int g[N][N]; bool st[N][N]; pii q[N*N]; int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};//按照题目的方向西北东南的方向 int bfs(int sx,int sy) { int hh=0,tt=0; q[0]={sx,sy}; st[sx][sy]=true; while(hh<=tt) { auto t=q[hh++];//取出队头 for(int i=0;i<4;i++)//枚举西北东南四个方向 { int a=t.x+dx[i],b=t.y+dy[i];//下一步 if(a<0||a>=n||b<0||b>=m) continue;//假如越界则continue if(st[a][b]) continue;//假如标记过则continue if((g[t.x][t.y]>>i)&1) continue;//假如是墙的话则continue st[a][b]=true;//标记这个点被标记过 q[++tt]={a,b};//把这个点放进队列用，以后用他来更新其他的房间 } } return tt+1;//返回房间数量 } int main() { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>g[i][j]; for(int i=0;i<n;i++)//遍历每一个点 for(int j=0;j<m;j++) if(!st[i][j])//假如之前没标记过，则是新的房间 { ans=max(ans,bfs(i,j));//更新一遍房间的最大值 cnt++;//水洼数量加一 } cout<<cnt<<endl; cout<<ans<<endl; return 0; }
3.山峰和山谷
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=1e3+10; int n; int g[N][N]; bool st[N][N]; pii q[N*N]; int bfs(int sx,int sy) { int hh=0,tt=0; bool up=false,low=false;//用来记录是不是山峰或者山谷 st[sx][sy]=true; q[0]={sx,sy}; while(hh<=tt) { auto t=q[hh++]; //因为是要周围八个方向，所以用枚举的方法 for(int i=t.x-1;i<=t.x+1;i++) for(int j=t.y-1;j<=t.y+1;j++) { if(i<0||i>=n||j<0||j>=n) continue;//假如越界 if(g[i][j]>g[t.x][t.y]) low=true;//假如是山谷 else if(g[i][j]<g[t.x][t.y]) up=true;//假如是山峰 else if(!st[i][j])//假如是同一高度且没被标记过的 { st[i][j]=true; q[++tt]={i,j}; } } } if(up&&low) return -1;//假如即使山峰并且又是山谷，则啥也不是 else if(up) return 1;//假如山峰 else if(low) return 0;//假如山谷 else return 2;//假如二者都可以 } int main() { int up=0,low=0; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>g[i][j]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(!st[i][j])//假如这个点没有被走过 { int t=bfs(i,j); if(t==1) up++;//假如是山峰 else if(t==0) low++;//假如是山谷 else if(t==2) up++,low++;//假如即可以作为山峰，又可以作为山谷 } cout<<up<<" "<<low<<endl; return 0; }
2最短路模型
1.迷宫问题
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=10; int n; int g[N][N]; bool st[N][N];//标记那个点被走过了 pii q[N*N],pre[N][N];//pre用来记录某个点的上一步 int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; void bfs(int sx,int sy) { int hh=0,tt=0; st[sx][sy]=true; q[0]={sx,sy}; pre[sx][sy]={0,0}; while(hh<=tt) { auto t=q[hh++]; for(int i=0;i<4;i++)//枚举四个方向 { int a=t.x+dx[i],b=t.y+dy[i]; if(a<0||a>=n||b<0||b>=n) continue;//假如越界 if(g[a][b]) continue;//假如是墙，不能走 if(st[a][b]) continue;//假如之前走过这个点 q[++tt]={a,b}; st[a][b]=true; pre[a][b]=t;//标记这个点由t转移过来的 } } } int main() { n=5; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>g[i][j]; bfs(n-1,n-1);//倒序求最短路 pii end(0,0);//正向输出路径 while(1) { printf("(%d, %d)\n",end.x,end.y); if(end.x==n-1&&end.y==n-1) break; end=pre[end.x][end.y]; } return 0; }
2.武士风度的牛
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=160; int n,m; char g[N][N]; int dist[N][N];//记录吗，每个点到起点的步数 pii q[N*N]; int dx[]={-1,1,2,2,1,-1,-2,-2},dy[]={2,2,1,-1,-2,-2,-1,1};//题目中的八个方向 int bfs(int sx,int sy,int ex,int ey) { int hh=0,tt=0; q[0]={sx,sy}; memset(dist,-1,sizeof dist); dist[sx][sy]=0; while(hh<=tt) { auto t=q[hh++]; for(int i=0;i<8;i++)//枚举八个方向 { int a=t.x+dx[i],b=t.y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue;//假如越界 if(g[a][b]=='*') continue;//假如是障碍，不能走 if(dist[a][b]!=-1) continue;//假如之前已经更新过这个点 q[++tt]={a,b}; dist[a][b]=dist[t.x][t.y]+1;//则步数+1 } } return dist[ex][ey];//返回到终点的步数 } int main() { cin>>m>>n; int sx,sy,ex,ey; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { cin>>g[i][j]; if(g[i][j]=='K') sx=i,sy=j;//标记起点 if(g[i][j]=='H') ex=i,ey=j;//标记终点 } cout<<bfs(sx,sy,ex,ey)<<endl;//输出最小步数 return 0; }
3.抓住那头牛
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,k; int dist[N];//记录每个点到起点的步数 int q[N]; int bfs() { int hh=0,tt=0; q[0]=n; memset(dist,-1,sizeof dist); dist[n]=0; while(hh<=tt) { int t=q[hh++]; if(t==k) return dist[k];//返回到起点的步数 if(t+1<N&&dist[t+1]==-1)//第一种情况走，且该位置没有被走过 { dist[t+1]=dist[t]+1;//则该点距离+1 q[++tt]=t+1;//将该点放进队列中 } if(t-1>=0&&dist[t-1]==-1)//第二种情况走，且该位置没有被走过 { dist[t-1]=dist[t]+1;//则该点距离+1 q[++tt]=t-1;//将该点放进队列中 } if(2*t<N&&dist[2*t]==-1)//第三种情况走，且该位置没有被走过 { dist[2*t]=dist[t]+1;//则该点距离+1 q[++tt]=2*t;//将该点放进队列中 } } return 0; } int main() { cin>>n>>k; cout<<bfs()<<endl;//输出最小步数 return 0; }
