P1596 [USACO10OCT]Lake Counting S

一篇比较水的题，我还是卡了好久， 其实一开始我用了stl队列写出来了，为了挑战一下自己，就决定分别用DFS，BFS（手写队列），BFS（queue）三种方法写了出来 ## DFS代码如下 ```cpp #include<iostream> #include<cstdio> #include<math.h> #include<algorithm> #include<cstring>//常规五行起步 using namespace std; char mapp[200][200];//建图（题目中是W与.用的是char数组） int m,n,ans=0; void dfs(int x,int y){//基本的dfs代码 mapp[x][y]='.';//先把该点置为.防止下次再搜到 int dx,dy; for(int i=-1;i<=1;i++){ for(int j=-1;j<=1;j++){//一开始想写8联通的，后来一直出的是120，就放弃了，改用的循环嵌套。 dx=x+i; dy=y+j; if(dx>=0&&dx<=n&&dy>=0&&dy<m&&mapp[dx][dy]=='W'){//判断是否在图里 dfs(dx,dy);//回溯 } } } return; } int main() { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>mapp[i][j]; //输入地图 for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(mapp[i][j]=='W')//如果有水，就进行判断，搜索。 { //cout<<i<<" "<<j<<endl; dfs(i,j); ans++;//水洼数+ 1 } cout<<ans;//输出结果 return 0; } ``` #### 上面就是dfs 然后bfs的主要部分是队列的判断，考虑队列中的头指针与尾指针 ```cpp ans++;//每次搜索+1 int head=0,tail=1,x,y,ans=0;//head是头，tail是尾 mapp[p][q]='.';//当前点置为已查 while(head<tail)//队列清空则此水洼搜索完成 { head++;//头+1 a[1][1]=p;//18 19行把当前点存入队列 a[1][2]=q; for(int i=1;i<=8;i++)//8联通搜索的基本 { x=a[head][1]+dx[i]; y=a[head][2]+dy[i]; if(x>=0&&x<=n&&y>=0&&y<=m&&mapp[x][y]=='W'){//在图内判断 tail++;//尾++ a[tail][1]=x; a[tail][2]=y; //cout<<" "<<x<<" "<<y<<endl; mapp[x][y]='.'; //当前点赋0 } } } ``` ## 上面的是对于bfs的代码 ## 这是手写的队列。 ## 然后ac的全体代码在下面- （用手写队列的话，这个题是有坑的，好像是第4个还是第几个点，它的输入数据是全部为W，所以 # 队列一定要开大） ```cpp #include<iostream> #include<cstdio> #include<math.h> #include<algorithm> #include<cstring>//常规5行 using namespace std; char mapp[200][200]; int dx[9]={0,0,0,1,1,1,-1,-1,-1},dy[9]={0,1,-1,0,1,-1,0,1,-1};//八连的判断 int a[10001][3];//队列 int n,m,ans; int bfs(int p,int q) { ans++;//每次搜索+1 int head=0,tail=1,x,y,ans=0;//head是头，tail是尾 mapp[p][q]='.';//当前点置为已查 while(head<tail)//队列清空则此水洼搜索完成 { head++;//头+1 a[1][1]=p;//18 19行把当前点存入队列 a[1][2]=q; for(int i=1;i<=8;i++)//8联通搜索的基本 { x=a[head][1]+dx[i]; y=a[head][2]+dy[i]; if(x>=0&&x<=n&&y>=0&&y<=m&&mapp[x][y]=='W'){//在图内判断 tail++;//尾++ a[tail][1]=x; a[tail][2]=y; //cout<<" "<<x<<" "<<y<<endl; mapp[x][y]='.'; //当前点赋0 } } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>mapp[i][j]; //建图 for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(mapp[i][j]=='W')//判断 { //cout<<i<<" "<<j<<endl; bfs(i,j);//搜索开始 } cout<<ans; return 0; } ``` ## 最后就是我利用queue写的代码了，这个代码是我当初在GXL大佬的帮助下写出来的， # 所以（感谢GXL大佬的教的广搜以及STL队列） ```cpp #include<iostream> #include<queue> using namespace std; char dd[115][115]; int mapp[115][115]; int go[9][2]{{0,0},{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}}; struct STU{ int xx; int yy; }; int m,n,qx,qy,tx,ty,ans; queue<STU>q; void bfs(int x,int y) { q.push((STU){x,y}); mapp[x][y]=0; while(q.size()!=0) { qx=q.front().xx; qy=q.front().yy; q.pop(); for(int i=1;i<=8;i++) { tx=qx+go[i][0]; ty=qy+go[i][1]; if(tx<1||tx>n||ty<1||ty>m) { continue; } if(mapp[tx][ty]==0) { continue; } mapp[tx][ty]=0; q.push((STU){tx,ty}); } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>dd[i][j]; if(dd[i][j]=='W') { mapp[i][j]=1; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mapp[i][j]==1) { ans++; bfs(i,j); } } } cout<<ans; return 0; } ``` 最后一个代码没写什么注释，凑合着看看吧， 这个题还是比较水的，所以我也没具体说明这个题的思路和解题过程~~（其实就是数水洼，以这个点为中心的九宫格内的水可与其构成一个水洼，计算最终水洼的数量）~~ 这个题大体就是这样，看在我辛苦码字的份上，就留个赞再走吧