我应该如何为我的 C++ 程序实现泛洪填充功能？

Question

我目前正在寻找像这样的东西：

.............
.............
..XXX.....X..
..XXX.....X..
..XXX........
..XXX........
..XXXXXXX....
..XXXXXXX....
..XXXXXXX....
.............
.............

进入这个：

.............
.............
..XXX.....O..
..XXX.....O..
..XXX........
..XXX........
..XXXXXXX....
..XXXXXXX....
..XXXXXXX....
.............
.............

用户输入 ./a.exe input4.txt floodfill 2 10 o

我相信我需要在程序中实现一些递归才能只查看与用户指针匹配的索引（包括上、下、左和右的位置），而不是读取整个向量（我不介意这样做，但不知道我将如何开始这样做）。

这是我目前拥有的洪水填充功能代码：

void floodfilll(vector<vector<char>> &vec, int x, int y, char r, char dum)
{
 int ii; 
 ii = 0;
 int jj; 
 jj = 0;
for (int i = 0; i < vec.size(); i ++) {
        for (int j = 0; j < vec[i].size(); j++) {
            if (vec[i][j] == r) {
                vec[i][j] == r;
                if ((i + ii) > 0) {
                    if (vec[i-1][j] == r)
                        vec[i-1][j] = dum;
                        vec[i][j] == r;
                    ii--;
                    floodfilll(vec, x + ii, y, r, dum);
                }
                if ((j + jj) > 0) {
                    if(vec[i][j-1] != r)
                        vec[i][j-1] = dum;
                        vec[i][j] == r;
                    jj--;
                    floodfilll(vec, x, y + jj, r, dum);
                }
                if ((i + ii)<vec.size()) {
                    if (vec[i+1][j] != r)
                        vec[i+1][j] = dum;
                        vec[i][j] == r;
                    ii++;
                    floodfilll(vec, x + ii, y, r, dum);
                }
                if ((j + jj)<vec[i].size()) {
                    if (vec[i][j+1] != r)
                        vec[i][j+1] = dum;
                        vec[i][j] == r;
                    jj++;
                    floodfilll(vec, x, y + jj, r, dum);
                }
            }
        }
        replacee(vec, dum, r);
    }
}

注意：我正在使用名为 replacee 的函数将 Var dum 替换为 Var R。Var dum 已分配 'i'，r 为 'X'。

此外，文本文件被解析为 char 的 2d 向量 (char)**

这正是我程序其余部分所基于的方式。这是替换函数：

    void replacee(vector<vector<char>> &vec, char oldd, char neww)
    {
        for (vector<char> &v : vec) // reference to innver vector
        {
            replace(v.begin(), v.end(), oldd, neww); // standard library algorithm
        }
    }

这是我正在使用的 int 主文件：

int main(int argc, char* argv[]) {

fstream fin; char ch;
string name (argv[1]); //File Name.
vector<vector<char>> data;
// 2D Vector.
vector<char> temp;
// Temporary vector to be pushed 
// into vec, since its a vector of vectors.
fin.open(name.c_str(),ios::in);
// Assume name as an arbitary file.
string argument2 (argv[2]);
while(fin)
{
    ch = fin.get();
    if(ch!='\n') {
        temp.push_back(ch);
    }
    else 
    { 
        data.push_back(temp); 
        temp.clear(); 
    }
}
if (argument2 == "floodfill") {
    string argument3 (argv[3]);
    string argument4 (argv[4]);
    string argument5 (argv[5]);
    int x = 0;
    int y = 0;
    stringstream xx(argument3);
    stringstream yy(argument4);
    xx >> x;
    yy >> y;
    floodfilll(data, x, y, argument5[0], 'i');
    for (int m = 0; m < data.size(); m ++) {
        for (int n = 0; n < data[m].size(); n++) {
            cout << data[m][n];
        }
        cout << endl;
    }
}

fin.close();
}

抱歉，如果我看起来只是为了抓取而粘贴代码，这是为了防止任何人有超出我的思维模式的解决方案。 int main 和 replacee 函数按预期工作。 我只是需要帮助想出一种方法使 floodfilll 正常工作。

这是我的代码得到的输出：

$ ./a.exe input4.txt floodfill 2 10 o
.............
.............
..XXX.....X..
..XXX.....X..
..XXX........
..XXX........
..XXXXXXX....
..XXXXXXX....
..XXXXXXX....
.............

Answer 1

为什么每次递归都要遍历整个字段？

正常情况下，洪水填充的工作方式如下：

你有一个特定的起点。
您用预期的颜色填充此起点
您检查四个（或 8 个，如果您还考虑对角线）邻居中的每一个，它们的颜色是否与起点最初的颜色相同；如果是这样，你继续递归。

所以实现可能如下所示：

void floodfill
(
        std::vector<std::vector<char>>& v,
        unsigned int x, unsigned int y, char r
)
{
    char p = v[x][y];
    v[x][y] = r;
    if(x > 0 && v[x - 1][y] == p)
        floodfill(v, x - 1, y, r);
    if(x + 1 < v.size() && v[x + 1][y] == p)
        floodfill(v, x + 1, y, r);
    if(y > 0 && v[x][y - 1] == p)
        floodfill(v, x, y - 1, r);
    if(y + 1 < v[x].size() && v[x][y + 1] == p)
        floodfill(v, x, y + 1, r);
}

请注意，我没有检查要填充的颜色是否与起始像素相同，我最初也没有检查 x 和 y 的范围检查。为了效率，我不会在递归函数中添加这些检查，而是在启动递归的特定入口函数中，因此它们只在需要时执行一次，而不会不必要地重复。

Answer 2

一个选项是使用递归，正如另一个答案所建议的那样。但是，我个人更喜欢在不必要的地方避免递归。另一种方法是基于队列的方法。

void floodfill (std::vector<std::vector<char>>& v, unsigned int x, unsigned int y, char r) {
    char init = v[x][y];
    if (init == r) return; //We don't want to get caught in an endless loop. 
    if (x >= v.size() || y >= v[x].size) return; //Index out of bounds. 
    std::queue<std::pair<unsigned int, unsigned int>> q;
    q.push(std::make_pair(x, y)); //Push the initial position into the queue.
    v[x][y] = r; //Replace the initial point. 
    while (!q.empty()) {//Keep looking at relevant neighbours so long as there is something in the queue. 
        auto pt = q.front(); //Collect the first entry.
        q.pop(); //Remove it, we don't want to keep processing the same point. 
        //Now add neighbours if they match our initial point. 
        if(pt.first > 0 && v[pt.first - 1][pt.second] == init)
            q.push(std::make_pair(pt.first - 1, pt.second);
            v[pt.first - 1][pt.second] = r; //Replace the value here to avoid pushing the same point twice. 
        if(pt.first + 1 < v.size() && v[pt.first + 1][pt.second] == init)
            q.push(std::make_pair(pt.first + 1, pt.second);
            v[pt.first + 1][pt.second] = r;
        if(pt.second > 0 && v[pt.first][pt.second - 1] == init)
            q.push(std::make_pair(pt.first, pt.second - 1);
            v[pt.first][pt.second - 1] = r;
        if(pt.second + 1 < v[pt.first].size() && v[pt.first][pt.second + 1] == init)
            q.push(std::make_pair(pt.first, pt.second + 1);
            v[pt.first][pt.second + 1] = r;
    }
}

这为您提供了一种无需递归的类似 BFS 的泛洪填充模式。或者，您也可以使用 stack 而不是 queue，然后填充将表现得更像 DFS（更类似于递归模式将执行的操作）。考虑到数据结构稍微简单一些，它甚至可能比队列表现得更好。

我应该如何为我的 C++ 程序实现泛洪填充功能？

How should I implement a flood fill function to my c++ program?

c++

vector

flood-fill