网站新闻详细页面设计,桓台网页定制,网站推广的常用方法有哪些,制作天下网站题目#xff1a;分析与解答 题目#xff1a;
多组案例#xff0c;每组案例输入一个m行n列的字符矩阵#xff0c;统计字符‘’组成多少个连通块。如果两个字符‘’所在的格子相邻#xff08;横、竖或对角线#xff09;#xff0c;则说明它们属于同一连通块。
Sample …题目分析与解答 题目
多组案例每组案例输入一个m行n列的字符矩阵统计字符‘’组成多少个连通块。如果两个字符‘’所在的格子相邻横、竖或对角线则说明它们属于同一连通块。
Sample Input 1 1*3 5**********1 8*****5 5************0 0Sample Output 0122分析与解答
1.找到油田然后通过循环遍历他周围的八个位置不断调用dfs函数如果连通则讲连通分量标号 2.循环找没标记过的油田然后继续进行1标号增加 3.油田均已标记完此时输出标号就是连通块个数
怎么写bfs 结束递归的条件有两个一个是超过了格子的范围另一个是之前曾经出现过以及这个格子不是油田。找的话每个油田做标号是同一联通区域的标上一样的号最后输出最终的标号即可。调用时机if(idx[i][j]0pic[i][j]’’)这个数没标记过而且属于油田。bfs里面用两个for循环直接把他八个方向都扫描了一遍并且如果满足条件就进行初始化此时如果在同一个连通区域他们的值是相同的所以main里调用bfs时一定是发现了不同的连通区域如果要求不同连通区域个数就只用在main里面更改cnt的个数
#includecstdio
#includecstring
using namespace std;
const int maxn 1005;
char pic[maxn][maxn];
int m,n,idx[maxn][maxn];void DFS(int r,int c,int id)
{if(r0||rm||c0||cn) return ;if(idx[r][c]0||pic[r][c]!) return ;idx[r][c]id;for(int dr-1;dr1;dr)for(int dc-1;dc1;dc)if(dr!0||dc!0)DFS(rdr,cdc,id);
}
int main()
{while(scanf(%d%d,m,n)!EOFmn){for(int i0;im;i) scanf(%s,pic[i]);memset(idx,0,sizeof(idx));int cnt0;for(int i0;im;i)for(int j0;jn;j)if(idx[i][j]0pic[i][j])DFS(i,j,cnt);printf(%d\n,cnt);}return 0;
}也可以写八条DFS调用 #includecstdio
#include cstring
using namespace std;
#define maxn 105
char a[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
void DFS(int x,int y)
{if(x0||xn||y0||ym) return ;if(a[x][y]*||vis[x][y]) return;vis[x][y]true;DFS(x1,y1);DFS(x1,y);DFS(x1,y-1);DFS(x,y-1);DFS(x-1,y-1);DFS(x-1,y);DFS(x-1,y1);DFS(x,y1);
}
int main()
{while(scanf(%d%d,n,m)!EOF){if(nm0) break;for(int i0; in; i)scanf(%s,a[i]);int sum0;memset(vis,false,sizeof(vis));for(int i0; in; i)for(int j0; jm; j)if(!vis[i][j]a[i][j]){DFS(i,j);sum;}printf(%d\n,sum);}return 0;
}
