UVA 572 -- Oil Deposits(DFS 求连通块)
图也有 DFS 和 BFS 遍历, 由于 DFS 更好写, 所以一般用 DFS 寻找连通块
下述代码用一个二重循环来找到当前格子的相邻 8 个格子, 也可用常量数组或者写 8 条 DFS 调用
下述算法是: 种子填充(floodfill)
两种连通区域
四连通区域: 从区域内一点出发, 可通过上下左右四个方向的移动组合, 在不越出区域的前提下, 能到达区域内的任意像素
八连通区域: 从区域内每一像素出发, 可通过八个方向, 即上下左右左上右上左下右下移动的组合, 在不越出区域的前提下, 能到达区域内的任意像素
基本原理
从多边形区域内部的某一像素点 (称为种子) 开始, 由此出发找到区域内的其它所有像素
采用的边界定义
区域边界上所有像素均具有某个特定的颜色值, 区域内部所有像素均不取这一特定颜色, 而边界外的像素则可具有与边界相同的颜色值
算法的执行过程:
从 (x,y) 开始, 先检测该点的颜色, 若它与边界色和填充色均不相同, 则用填充色填充该点然后检测相邻位置, 以确定它们是否是边界色和填充色, 若不是, 则填充该相邻点直到检测完区域边界范围内的所有像素为止
从当前点检测相邻像素的方法: 四连通或八连通
从四个方向寻找下一个像素, 称为四向算法(只能填充四连通区域);
从八个方向寻找下一个像素, 称为八向算法(可以填充八连通区域和四连通区域)
四连通区域的种子填充递归算法:
- void ZhongZiTC4 (int seedx, int seedy, int fcolor, int bcolor)
- {
- int current = getpixel (seedx, seedy);
- if ((current != bcolor) && (current != fcolor))
- { putpixel (seedx, seedy, fcolor);
- ZhongZiTC4 (seedx+1, seedy, fcolor, bcolor); // 右
- ZhongZiTC4 (seedx1, seedy, fcolor, bcolor); // 左
- ZhongZiTC4 (seedx, seedy+1, fcolor, bcolor); // 上
- ZhongZiTC4 (seedx, seedy1, fcolor, bcolor); // 下
- }
- }
UVA 572 代码:
- #include<iostream>
- #include<cstring>
- using namespace std;
- const int maxn = 100+5;
- char deposits[maxn][maxn];
- int id[maxn][maxn];
- int rm,cm;
- void dfs(int r,int c,int cnt)
- {
- /// 判断是否出界
- if(r<0 || r>=rm || c<0 || c>=cm) return;
- /// 临界条件
- if(deposits[r][c] == *) return;
- if(id[r][c]) return;
- id[r][c] = cnt;
- for(int i=-1;i<=1;i++)
- for(int j=-1;j<=1;j++)
- if(i!=0 || j!=0) dfs(r+i,c+j,cnt);
- }
- int main()
- {
- while(cin>>rm>>cm && rm && cm)
- {
- for(int i=0;i<rm;i++) cin>>deposits[i];
- int cnt=0;
- memset(id,0,sizeof(id));
- for(int i=0;i<rm;i++)
- for(int j=0;j<cm;j++)
- {
- if(!id[i][j] && deposits[i][j]==@)/// 没有编号
- dfs(i,j,++cnt);
- }
- cout<<cnt<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2499370.html