C++

Question

我正在使用 Eclipse IDE 在 C++ 中创建一个 flood fill 算法。该算法包含一个称为 image 的向量向量。根据用户输入在此图像中绘制一个正方形，将图像分割为两个区域（正方形内部和外部）。 A clicked point 作为输入。如果该点在正方形内部，则正方形内的所有点都将更改为 fill_value（在本例中为 25）。如果在正方形外，则正方形外的所有像素变为fill_value。这是代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstddef>
#include <stdexcept>

class Point
{
    std::size_t x_cord;
    std::size_t y_cord;
public:
    Point(std::size_t x, std::size_t y):x_cord{x}, y_cord{y}
    {

    }
    std::size_t x() const
    {
        return x_cord;
    }
    std::size_t y() const
    {
        return y_cord;
    }

};

bool check_point(Point pt, std::size_t x_dim, std::size_t y_dim)
{
    if(pt.x() >= 0 && pt.x() < x_dim && pt.y() >= 0 && pt.y() < y_dim)
    {
        return true;
    }
    return false;
}

void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val)
{
    std::vector<Point> neighbors;
    std::size_t x_dim = image.size();
    std::size_t y_dim;
    if(x_dim > 0)
    {
        y_dim = image[0].size();
    }
    if(check_point(Point{curr_point.x() - 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val)
    {
        q.push(Point{curr_point.x() - 1, curr_point.y()});
    }
    if(check_point(Point{curr_point.x(), curr_point.y() - 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val)
    {
        q.push(Point{curr_point.x(), curr_point.y() - 1});
    }
    if(check_point(Point{curr_point.x() + 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val)
    {
        q.push(Point{curr_point.x() + 1, curr_point.y()});
    }
    if(check_point(Point{curr_point.x(), curr_point.y() + 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val)
    {
        q.push(Point{curr_point.x(), curr_point.y() + 1});
    }
}

void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val)
{
    int old_val = image[clicked.x()][clicked.y()];
    std::queue<Point> q;
    q.push(clicked);
    while(!q.empty())
    {
        Point curr_point = q.front();
        get_neighbors(curr_point, q, image, old_val);
        image[curr_point.x()][curr_point.y()] = new_val;
        q.pop();
    }
}

void draw_square(std::vector<std::vector<int>>& image, Point top_left_corner, int length)
{
    std::size_t x_0 = top_left_corner.x();
    std::size_t y_0 = top_left_corner.y();
    std::size_t x;
    std::size_t y;
    for(x = x_0; x < x_0 + length; x++)
    {
        image[x][y_0] = 1;
        image[x][y_0 + length - 1] = 1;
    }
    for(y = y_0; y < y_0 + length; y++)
    {
        image[x_0][y] = 1;
        image[x_0 + length - 1][y] = 1;
    }
}

void print_image(std::vector<std::vector<int>>& image, std::size_t x_dim, std::size_t y_dim)
{
    for(std::size_t i = 0; i < x_dim; i++)
    {
        for(std::size_t j = 0; j < y_dim; j++)
        {
            std::cout << image[i][j] << "\t";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

int main()
{
    try
    {
        std::size_t x_dim, y_dim;
        std::size_t x, y;
        std::size_t c_x = 0;
        std::size_t c_y = 0;
        int length;
        int fill_value = 25;
        std::cout << "Enter the dimensions of the image: \n";
        std::cin >> x_dim >> y_dim;
        std::vector<std::vector<int>> image(x_dim, std::vector<int>(y_dim, 0));
        std::cout << "Enter the top left point coordinates and length for the square: \n";
        std::cin >> x >> y >> length;
        Point top_left_corner{x, y};
        if(!check_point(top_left_corner, x_dim, y_dim) || !check_point(Point{top_left_corner.x() + length - 1, top_left_corner.y() + length - 1}, x_dim, y_dim))
        {
            throw std::out_of_range{"Invalid Access"};
        }
        draw_square(image, top_left_corner, length);
        std::cout << "Before Flood Fill: \n";
        print_image(image, x_dim, y_dim);
        std::cout << "Enter point to be clicked: \n";
        std::cin >> c_x >> c_y;
        Point clicked{c_x, c_y};
        //std::cout << "here1\n";
        if(!check_point(clicked, x_dim, y_dim))
        {
            throw std::out_of_range{"Invalid Access"};
        }
        std::cout << "here2\n";
        flood_fill(image, clicked, fill_value);
        std::cout << "After Flood Fill: \n";
        print_image(image, x_dim, y_dim);
    }
    catch(std::out_of_range& e)
    {
        std::cerr << e.what() << "\n";
    }
    return 0;
}

它对某些输入工作正常。但是，请考虑以下输入（Before Flood Fill 之后的数组是程序输出，而不是输入）：

Enter the dimensions of the image: 
20 20
Enter the top left point coordinates and length for the square: 
15 15 4
Before Flood Fill: 
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1   0   
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   

Enter point to be clicked: 
1 2

此后程序占用大量处理，不会继续或不会终止。我的想法是，这是由于 flood_fill 函数的执行效率低下造成的。当我使用调试器时，std::cout << "here2\n"; 语句在控制台上打印 here2，而当我只是运行程序时它不会打印。所以，我不确定是 flood_fill 导致了这个问题还是其他原因。

为什么运行宁和调试时行为不同？
请提供调试建议

注意：我的想法是，由于值正在更改，他们将自动无法通过成为合格邻居的检查。但是我发现我的代码有问题。到时候，值发生变化，一个特定的邻居可能会被添加很多次。这两个答案都帮助我确定了这一点。谢谢你们。

Answer 1

std::size_t 是无符号整型。当它达到负值时，它会返回到最大值，即正值。因此，您所有的 x >= 0 和 y >= 0 始终为真。尝试将所有 size_t 换成 int.

您的另一个问题是您的洪水填充队列已经达到了巨大的规模。这是因为添加点的速度快于删除点的速度。你需要一些方法来判断一个点之前是否被洪水填充：

void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val, std::vector<std::vector<bool>> &visited)
{
  std::vector<Point> neighbors;
  int x_dim = image.size();
  int y_dim;
  if (x_dim > 0)
  {
    y_dim = image[0].size();
  }
  if (check_point(Point{ curr_point.x() - 1, curr_point.y() }, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val && !visited[curr_point.x() - 1][curr_point.y()])
  {
    q.push(Point{ curr_point.x() - 1, curr_point.y() });
    visited[curr_point.x() - 1][curr_point.y()] = true;
  }
  if (check_point(Point{ curr_point.x(), curr_point.y() - 1 }, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val && !visited[curr_point.x()][curr_point.y() - 1])
  {
    q.push(Point{ curr_point.x(), curr_point.y() - 1 });
    visited[curr_point.x()][curr_point.y() - 1] = true;
  }
  if (check_point(Point{ curr_point.x() + 1, curr_point.y() }, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val && !visited[curr_point.x() + 1][curr_point.y()])
  {
    q.push(Point{ curr_point.x() + 1, curr_point.y() });
    visited[curr_point.x() + 1][curr_point.y()] = true;
  }
  if (check_point(Point{ curr_point.x(), curr_point.y() + 1 }, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val && !visited[curr_point.x()][curr_point.y() + 1])
  {
    q.push(Point{ curr_point.x(), curr_point.y() + 1 });
    visited[curr_point.x()][curr_point.y() - 1] = true;
  }
}

void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val)
{
  if (image.empty()) return;
  int old_val = image[clicked.x()][clicked.y()];
  std::vector<std::vector<bool>> visisted(image.size(), std::vector<bool>(image[0].size(), false));
  std::queue<Point> q;
  q.push(clicked);
  while (!q.empty())
  {
    Point curr_point = q.front();
    get_neighbors(curr_point, q, image, old_val, visisted);
    image[curr_point.x()][curr_point.y()] = new_val;
    q.pop();
  }
}

Answer 2

你的回溯太糟糕了。队列中充满了数百万个重复点。您应该在每次迭代时标记所有收集的点，这样它们就不会再次添加到队列中：

void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val, int new_val)
{
    std::size_t x_dim = image.size();
    std::size_t y_dim;
    if(x_dim > 0)
    {
        y_dim = image[0].size();
    }
    image[curr_point.x()][curr_point.y()] = new_val;
    if(check_point(Point{curr_point.x() - 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val)
    {
        q.push(Point{curr_point.x() - 1, curr_point.y()});
        image[q.back().x()][q.back().y()] = new_val;
    }
    if(check_point(Point{curr_point.x(), curr_point.y() - 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val)
    {
        q.push(Point{curr_point.x(), curr_point.y() - 1});
        image[q.back().x()][q.back().y()] = new_val;
    }
    if(check_point(Point{curr_point.x() + 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val)
    {
        q.push(Point{curr_point.x() + 1, curr_point.y()});
        image[q.back().x()][q.back().y()] = new_val;
    }
    if(check_point(Point{curr_point.x(), curr_point.y() + 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val)
    {
        q.push(Point{curr_point.x(), curr_point.y() + 1});
        image[q.back().x()][q.back().y()] = new_val;
    }
}

void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val)
{
    int old_val = image[clicked.x()][clicked.y()];
    if(old_val == new_val)
    {
         return;
    }
    std::queue<Point> q;
    q.push(clicked);
    while(!q.empty())
    {
        Point curr_point = q.front();
        get_neighbors(curr_point, q, image, old_val, new_val);
        q.pop();
    }
}

C++ - 调试时 Eclipse 的行为与运行不同

C++ - Eclipse behavior is different while debugging and running

eclipse

debugging

flood-fill

C++ - 调试时 Eclipse 的行为与 运行 不同

C++ - Eclipse behavior is different while debugging and running

c++

eclipse

debugging

flood-fill

C++ - 调试时 Eclipse 的行为与运行不同