Windless
订阅/Feed
稗田千秋(i@wind.moe)

Flood Fill

稗田千秋
Apr.09 2016 algorithm

Flood Fill(洪水填充)是计算机图形学的一种填充算法,用于将一个区域中连通的同色点染成相同颜色,原理很简单,非常像搜索,即从一个点向周围寻找符合条件的点填充遍历,最常见的有四路填充法(4-Way Recursive Method),八路填充法(8-Way Recursive Method)和基于扫描线的填充法(Recursive Scanline),根据实现又能分为基于递归和基于栈。笔者不是图形学方向的,这里仅涉及可能使用到的四路填充法。

基于递归的四路填充算法实现

代码很简单,就是在深度搜索的基础上加个标记,取一个种子像素点,向其四个邻域拓展,满足条件时则对其进行染色,不断重复这个行为,但也容易由于递归导致栈溢出。

void floodFill4(int x, int y, int newColor, int oldColor){
  if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor){
    screenBuffer[y][x] = newColor;
    floodFill4(x + 1, y, newColor, oldColor);
    floodFill4(x - 1, y, newColor, oldColor);
    floodFill4(x, y + 1, newColor, oldColor);
    floodFill4(x, y - 1, newColor, oldColor);
  }
}

部分题解

QDUOJ 7 - GZS与小公园

某天GZS漫步在学校新建的小公园,他发现那里建成了一些水池和小河道。我们暂且把它们统一看成水池。假设公园旁有一张小公园的地图,上面仅标识了此处是否是水池,你能帮GZS计算出该地图中一共有几个水池吗。

 #include <cstdio>
#include <cstring>
#define bool int
#define true 1
#define false 0
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int poor[105][105];
int t, m, n, color;
int direction[4][2] = { 0,1,1,0,-1,0,0,-1 };
bool valid(int x, int y, int oldColor) {
    if (x < 0 || y < 0 || x >= m || y >= n || poor[x][y] != oldColor)
        return false;
    return true;
}
void floodfill(int x,int y,int oldColor,int newColor) {
    if (!valid(x, y, oldColor))
        return;
    poor[x][y] = newColor;
    for (int i = 0; i < 4; i++)
        floodfill(x+direction[i][0], y+direction[i][1], oldColor, newColor);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &m, &n);
        color = 0;
        MEM(poor, 0);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &poor[i][j]);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if(valid(i, j, 1))
                    color++,floodfill(i, j, 1, 0);
        printf("%d\n", color);
    }
}
--END--
文章创建于 2016-04-09 11:58:47,最后更新 2016-04-09 11:58:47
Comment
尝试加载Disqus评论, 失败则会使用基础模式.
    • play_arrow

    About this site

    version:1.02 Alpha
    博客主题: Lime
    联系方式: i@wind.moe
    写作语言: zh_CN & en_US
    博客遵循 CC BY-NC-SA 4.0许可进行创作

    此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方