UVA 572 -- Oil Deposits（DFS求连通块+种子填充算法）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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+, seedy, fcolor, bcolor); //右
ZhongZiTC4 (seedx–, seedy, fcolor, bcolor); //左
ZhongZiTC4 (seedx, seedy+, fcolor, bcolor); //上
ZhongZiTC4 (seedx, seedy–, fcolor, bcolor); //下
}
}

UVA 572代码：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = +;
char deposits[maxn][maxn];
int id[maxn][maxn];
int rm,cm;
void dfs(int r,int c,int cnt)
{
///判断是否出界
if(r< || r>=rm || c< || c>=cm) return;
///临界条件
if(deposits[r][c] == '*') return;
if(id[r][c]) return; id[r][c] = cnt;
for(int i=-;i<=;i++)
for(int j=-;j<=;j++)
if(i!= || j!=) dfs(r+i,c+j,cnt); } int main()
{ while(cin>>rm>>cm && rm && cm)
{
for(int i=;i<rm;i++) cin>>deposits[i];
int cnt=;
memset(id,,sizeof(id));
for(int i=;i<rm;i++)
for(int j=;j<cm;j++)
{
if(!id[i][j] && deposits[i][j]=='@')///没有编号
dfs(i,j,++cnt);
}
cout<<cnt<<endl; }
return ;
}