c++ Floodfill算法最终错误

Question

我的 floodfilling 算法快完成了，但是某处有一个小错误，我花了大约 3 个小时调试，但我似乎找不到它!

注意: 在阅读时，我使用 0 到 15 之间的数字来定义墙壁

1 = 顶部 2 = 正确 4 = 底部 8 = 左 (所以 13 意味着顶/底/左墙都在那里)

我的程序:

• 它读取字段数以计算最大的房间(因此下面的所有内容都是一个循环，根据字段数重复)。

• 然后获取房间的尺寸

• 现在在类字段中，它创建了一个对象数组(Cell)，它存储周围的墙壁(从左到右，从上到下)，以及一个小于 16 的值

• 现在我认为问题出在这里，通过 std::cin 读取值

• 然后当所有内容都读入时，它会扫描空的 (0)，然后创建一个房间，并检查它周围的可用空间(使用墙检查)

• 最后它返回最大值，我们就完成了。

我使用的输入:

1
2 2
13 3
15 14

所以发生的事情是某处，在墙壁检查中，或对象 Cell 的创建出了问题(我认为)

这是我的脚本，很抱歉不得不问这样愚蠢的问题!

提前致谢

    // een simpele floodfill

    #include <stdlib.h>
    #include <iostream>
    #include <bitset>


class Cell {

    private:
      int  kamer, value;
      bool left, right, up, down;

    public:            
      // constructor
      Cell::Cell() {};
      // functions
      bool CanLeft()      { return left ; }
      bool CanRight()     { return right; }
      bool CanDown()      { return down ; }
      bool CanUp()        { return up   ; }
      int  GetRoom()       { return kamer; }
      void SetRoom(int x)  { kamer = x   ; }      
      void SetValue(int x, int room=0) { value  = x;
                             kamer = room;
                             std::bitset<sizeof(int)> bits(value); 
                             if (bits[3]) left  = true;
                             else         left  = false;
                             if (bits[2]) down  = true;
                             else         down  = false;
                             if (bits[1]) right = true;
                             else         right = false;
                             if (bits[0]) up    = true;
                             else         up    = false;
                           }
};

class Field {

    private:
      int Biggest_Chamber;
      int Y;
      int X;
      int temp;
      Cell playfield[][1];

    public:
      // constructor
      Field::Field(int SizeY, int SizeX) {
                    Y = SizeY;
                    X = SizeX;
                    Cell playfield[SizeY-1][SizeX-1];
                    }
      // Create a 2d array and fill it

      void Get_input() {

           for (int Yas = 0; Yas < Y; Yas++){

               for (int Xas = 0; Xas < X; Xas++){

                   std::cin >> temp;
                   playfield[Yas][Xas].SetValue(temp);         
               }
           } 
      };  
      void Start() { Mark(0,0,1); }

      void Mark(int y, int x, int nr) {
                  std::cout << nr;
                  temp = nr;
                  playfield[y][x].SetRoom(nr);
                  if (playfield[y][x].CanLeft())   {
                     if (playfield[y][x-1].GetRoom() != 0) {
                                                    Mark(y, x-1, nr);
                                                    std::cout << nr;
                                                    system("pause");}}
                  if (playfield[y][x].CanDown()) {
                     if (playfield[y+1][x].GetRoom() != 0) {
                                                    Mark(y+1, x, nr);
                                                    std::cout << nr;
                                                    system("pause");}}
                  if (playfield[y][x].CanRight())  {
                     if (playfield[y][x+1].GetRoom() != 0) {
                                                    Mark(y, x+1, nr);
                                                    std::cout << nr;
                                                    system("pause");}}
                  if (playfield[y][x].CanUp())   {
                     if (playfield[y-1][x].GetRoom() != 0) {
                                                    Mark(y-1, x, nr);
                                                    std::cout << nr;
                                                    system("pause");}} 
                  for (int vertical = 0; vertical < Y; vertical++) {
                      for (int horizontal = 0; horizontal < X; horizontal++) {
                          if (playfield[vertical][horizontal].GetRoom() == 0) Mark(vertical, horizontal, nr+1);                   
                      }      
                  }
      }         
      int MaxValue() {
          int counter[temp];
          int max = 0;

          for (int y = 0; y < Y; y++) {
              for (int x = 0; x < X; x++) {
                  counter[playfield[y][x].GetRoom()]++;
              }
          }

          for (int i = 0; i < temp; i++)
          {
              if (counter[i] > max)
                 max = counter[i];
          }

          return max;
     }            
};


    int main() {
    using namespace std;


    int NrKamers;
    int sizeY;
    int sizeX;

    std::cin >> NrKamers;
    for (int i = 0; i < NrKamers; i++){

        std::cin >> sizeY >> sizeX;

        Field floodfield(sizeY, sizeX);
        floodfield.Get_input();
        floodfield.Start();

        std::cout << floodfield.MaxValue() << std::endl;
    }
    return 0;
}

Answer 1

我没有太多时间来处理代码，但我的第一印象是你没有标记(或者更确切地说没有使用标记)数组中每个访问过的位置，这样你就可以朝一个方向移动，而同时处理您返回到原始方 block 的其他位置。考虑以下测试顺序:左、右、上、下；并且您从左上角开始:

你不能向左移动，但你可以向右移动。在第二个递归级别，您可以向左移动并返回到第一个方 block 。然后你不能向左移动，但你可以向右移动，所以你回到方格二，从那里你移动到方格一......无限。

在你移动到下一个方 block 之前，你必须将你的方 block 标记为已访问，并检查你打算移动到的方 block 在当前运行中是否没有被访问过。

段错误是无限递归的结果，在你耗尽堆栈之后。