首页 > 代码库 > ACM:图的DFS,黑白图像
ACM:图的DFS,黑白图像
题目:输入一个n*n的黑白图像(1表示黑色,0表示白色),任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个八连块。
输入:第一行输入一个整数n(n<=500),下面输入n行,每行是由n个0或1组成的字符串。
输出:输出有多少个八连块,以及每个块的面积。一个方格的面积为1。
分析:把图片最外层扩展开来,在最外面加一层白色的框框。。设置一个数组来存储每个八连块的面积。。DFS递归调用每一个黑色的方块。。DFS的最后一个参数要设置为传递引用。。
#include <iostream> #include <string> using namespace std; const int MAXN = 500; int maze[MAXN][MAXN], vis[MAXN][MAXN]; int mianji[MAXN]; void dfs(int x, int y, int &mianji) { if(vis[x][y] || !maze[x][y]) return; mianji++; vis[x][y] = 1; dfs(x-1, y-1, mianji); dfs(x-1, y, mianji); dfs(x-1, y+1, mianji); dfs(x, y-1, mianji); dfs(x, y+1, mianji); dfs(x+1, y-1, mianji); dfs(x+1, y, mianji); dfs(x+1, y+1, mianji); return; } int main() { int n; cin >> n; string str; memset(maze, 0, sizeof(maze)); for(int i = 0; i < n; ++i) { cin >> str; for(int j = 0; j < n; ++j) { maze[i+1][j+1] = str[j] - '0'; } } memset(vis, 0, sizeof(vis)); memset(mianji, 0, sizeof(mianji)); int ans = 0; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(!vis[i][j] && maze[i][j]) { dfs(i, j, mianji[ans]); ans++; } } } cout << ans << endl; for(int i = 0; i < ans; ++i) { cout << mianji[i] << endl;; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。