高性能网站建设进阶指南 pdf,盐城建设厅网站设计备案,建设网站的个人心得,wordpress弹窗公告【题目来源】 https://oj.czos.cn/p/1435 https://www.acwing.com/problem/content/1099/ 【题目描述】 农夫约翰的农场可以表示成 NM#xff08;1≤N, M≤100#xff09;个方格组成的矩形。由于近日的降雨#xff0c;在约翰农场上的不同地方形成了池塘。 每一个方格或者有…【题目来源】https://oj.czos.cn/p/1435https://www.acwing.com/problem/content/1099/【题目描述】农夫约翰的农场可以表示成 N×M1≤N, M≤100个方格组成的矩形。由于近日的降雨在约翰农场上的不同地方形成了池塘。每一个方格或者有积水W或者没有积水.。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格每一个方格周围的八个方格都被认为是与这个方格相连的。现给出约翰农场的图样要求输出农场上的池塘数。【输入格式】第 1 行由空格隔开的两个整数N 和 M第 2~N1行每行 M 个字符代表约翰农场的一排方格的状态。每个字符或者是 W 或者是 .字符之间没有空格。【输出格式】输出只有 1 行输出约翰农场上的池塘数。【输入样例】10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.【输出样例】3【数据范围】1≤N, M≤100【算法分析】● 本题代码与“AcWing 1097池塘计数https://blog.csdn.net/hnjzsyjyj/article/details/118642238”的代码一模一样。【算法代码一dfs】#include bits/stdc.h using namespace std; const int N1e35; char mp[N][N]; int dx[] {1,1,0,-1,-1,-1,0,1}; int dy[] {0,1,1,1,0,-1,-1,-1}; int n,m,ans; void dfs(int x,int y) { /*Mark the current position as . to indicate that it has been visited, in order to avoid redundant processing.*/ mp[x][y].; for(int i0; i8; i) { int txxdx[i]; int tyydy[i]; if(mp[tx][ty]W) { dfs(tx,ty); } } } int main() { cinnm; for(int i0; in; i) { for(int j0; jm; j) { cinmp[i][j]; } } for(int i0; in; i) { for(int j0; jm; j) { if(mp[i][j]W) { dfs(i,j); ans; } } } coutansendl; return 0; } /* in: 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. out: 3 */【算法代码二bfs】#includebits/stdc.h using namespace std; typedef pairint,int PII; const int N1e35; char mp[N][N]; int dx[] {1,1,0,-1,-1,-1,0,1}; int dy[] {0,1,1,1,0,-1,-1,-1}; int n,m,ans; void bfs(int x,int y) { queuePII q; q.push({x,y}); mp[x][y].; while(!q.empty()) { PII tq.front(); q.pop(); for(int i0; i8; i) { int txt.firstdx[i]; int tyt.seconddy[i]; if(tx0 ty0 txn tym mp[tx][ty]W) { mp[tx][ty].; q.push({tx,ty}); } } } } int main() { cinnm; for(int i0; in; i) { for(int j0; jm; j) { cinmp[i][j]; } } for(int i0; in; i) { for(int j0; jm; j) { if(mp[i][j]W) { bfs(i,j); ans; } } } coutansendl; return 0; } /* in: 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. out: 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/118642238https://blog.csdn.net/hnjzsyjyj/article/details/158618461