c++ - 词搜索算法段错误

Question

我已经研究单词搜索算法很长时间了，我认为我做得很好并决定测试极限。我创建了一个程序，它可以使文件尽可能大。所以我做了一个矩阵 10000 * 10000(10000000 个字母)和从左上角到右下角的非常长的单词。事情是它适用于 4000 * 4000 矩阵但是它变得更大它只是崩溃。我试图评论所有其他检查可能的位置并留下正确的检查，即使使用 10000 * 10000 矩阵它也能完美工作，但一旦我添加其他检查它就会停止，我不知道为什么。有什么建议吗？

我的代码:

    #include <iostream>     //Might Be:
    #include <string>       // <----->
    #include <fstream>      // /-\  (1)/\               /\(3)
    #include <new>          //  |       \               /
    #include <cstdlib>      //  |        \             /
                            //  |         \           /
                            //  |          \         /
                            //  |           \       /
                            // \_/       (2)\/     \/(4)
                            //

    using namespace std;
                                        //Loop[4] //Loop[5]
    int * Possibles(int Widht, int Height, int Poz, int Poz1, int Leng, int * Possible)
    {
        if(Poz1 < Widht - Leng + 1) // To right
        {
            Possible[0] = 1;
        }

        if(Poz1 >= Leng - 1) // To left
        {
            Possible[1] = 1;
        }

        if(Poz <= Height - Leng) // From top to bottom
        {
            Possible[2] = 1;
        }

        if(Poz >= Leng) // From bottom to top
        {
            Possible[3] = 1;
        }

        if(Poz + Leng <= Height && Poz1 + Leng <= Widht) //(2)
        {
            Possible[4] = 1;
        }

        if(Poz + Leng <= Height && Poz1 - Leng + 1 >= 0) //(4)
        {
            Possible[5] = 1;
        }

        if(Poz - Leng + 1 >= 0 && Poz1 - Leng + 1 >= 0) //(1)
        {
            Possible[6] = 1;
        }

        if(Poz - Leng + 1 >= 0 && Poz1 + Leng <= Widht) //(3)
        {
            Possible[7] = 1;
        }

        return Possible;
    }

    int * Zero(int * Possible)
    {
            Possible[0] = 0;
            Possible[1] = 0;
            Possible[2] = 0;
            Possible[3] = 0;
            Possible[4] = 0;
            Possible[5] = 0;
            Possible[6] = 0;
            Possible[7] = 0;

            return Possible;
    }

    string Next(string * NewMatrix, int Height, int Widht)
    {
        return NewMatrix[Height].substr(Widht, 1);
    }

    bool Find(string Word, int Poz, int Poz1, int Look, string Have, string * Matrix, int * Possible, int Backup, int Backup1)
    {
        if(Have == Word)
        {
            return true;
            return Possible;
        }

        string NewLet = Word.substr(Look, 1);

        if(Possible[0] == 1)
        {
            if(NewLet == Next(Matrix, Poz, Poz1 + 1))
            {
                Have += NewLet;

                return Find(Word, Poz, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[0] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[1] == 1)
        {
            if(NewLet == Next(Matrix, Poz, Poz1 - 1))
            {
                Have += NewLet;

                return Find(Word, Poz, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[1] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[2] == 1)
        {
            if(NewLet == Next(Matrix, Poz + 1, Poz1))
            {
                Have += NewLet;

                return Find(Word, Poz + 1, Poz1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[2] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[3] == 1)
        {
            if(NewLet == Next(Matrix, Poz - 1, Poz1))
            {
                Have += NewLet;

                return Find(Word, Poz - 1, Poz1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[3] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[4] == 1)
        {
            if(NewLet == Next(Matrix, Poz + 1, Poz1 + 1))
            {
                Have += NewLet;

                return Find(Word, Poz + 1, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[4] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[5] == 1)
        {
            if(NewLet == Next(Matrix, Poz + 1, Poz1 - 1))
            {
                Have += NewLet;

                return Find(Word, Poz + 1, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[5] = 0;

                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[6] == 1)
        {
            if(NewLet == Next(Matrix, Poz - 1, Poz1 - 1))
            {
                Have += NewLet;

                return Find(Word, Poz - 1, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[6] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        if(Possible[7] == 1)
        {
            if(NewLet == Next(Matrix, Poz - 1, Poz1 + 1))
            {
                Have += NewLet;

                return Find(Word, Poz - 1, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1);
            }
            else
            {
                Possible[7] = 0;
                Have = Word.substr(0, 1);

                return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1);
            }
        }

        return false;
    }

    string Diro(int * Possible)
    {
        string Dir;

        bool Next = true;

        if(Possible[0] == 1 && Next == true)
        {
            Dir = " From right to left";
            Next = false;
        }

        if(Possible[1] == 1 && Next == true)
        {
            Dir = " From left to right";
            Next = false;
        }

        if(Possible[2] == 1 && Next == true)
        {
            Dir = " From top to bottom";
            Next = false;
        }

        if(Possible[3] == 1 && Next == true)
        {
            Dir = " From bottom to top";
            Next = false;
        }

        if(Possible[4] == 1 && Next == true)
        {
            Dir = " ";
            Next = false;
        }

        if(Possible[5] == 1 && Next == true)
        {
            Dir = " ";
            Next = false;
        }

        if(Possible[6] == 1 && Next == true)
        {
            Dir = " ";
            Next = false;
        }

        if(Possible[7] == 1 && Next == true)
        {
            Dir = " ";
            Next = false;
        }

        return Dir;
    }

    int main()
    {
        int Height = 0, Widht = 0, Numb = 0;

        int Loop[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};

        int * Possible = new int[8];

        string Dir, Search, Tempo, Temp;

        ifstream Data("C:/Users/Magician/AppData/Local/VirtualStore/Program Files (x86)/CodeBlocks/MakeMaze/Files/Maze.txt");

        Data >> Widht >> Height;

        string * NewMatrix = new string[Height];

        while(Loop[7] < Height)
        {
            Tempo = "";
            Loop[8] = 0;

            while(Loop[8] < Widht)
            {
                Data >> Temp;
                Tempo += Temp;
                Loop[8]++;
            }

            NewMatrix[Loop[7]] = Tempo;

            Loop[7]++;
        }

        Data >> Numb;

        string * Words = new string[Numb];

        while(Loop[2] < Numb)
        {
            Data >> Words[Loop[2]];

            Loop[2]++;
        }

        Data.close();

        while(Loop[3] < Numb)
        {
            Search = Words[Loop[3]].substr(0, 1);
            Loop[4] = 0;

            while(Loop[4] < Height)
            {
                Loop[5] = 0;

                while(Loop[5] < Widht)
                {
                    if(NewMatrix[Loop[4]].substr(Loop[5], 1) == Search)
                    {
                        Zero(Possible);
                        Possibles(Widht, Height, Loop[4], Loop[5], Words[Loop[3]].size(), Possible);

                        if(Find(Words[Loop[3]], Loop[4], Loop[5], 1, Search, NewMatrix, Possible, Loop[4], Loop[5]))
                        {
                            cout << Words[Loop[3]] << " At: " << Loop[4] + 1 << " collumn, symbol " << Loop[5] + 1 << " " << Diro(Possible) << endl;

                            Loop[5] = Widht;
                            Loop[4] = Height;
                        }
                    }

                    Loop[5]++;
                }

                Loop[4]++;
            }

            Loop[3]++;
        }

        delete [] Possible;
        delete [] Words;
        delete [] NewMatrix;

        return 0;
    }

如果你不明白我之前写的:当我评论每个 if(Possible[] == ) 除了函数 Find() 中的 if(Possible[5] == 1) 算法有效然后所有允许它不。我尝试使用 100 * 100 矩阵查找很多单词，一切正常。

Answer 1

1. Possibles 中的一个条件不正确:

   /* INCORRECT: Should be  [ Poz >= Leng - 1 ] */
   if(Poz >= Leng) // From bottom to top
   {
       Possible[3] = 1;
   }
   

   但这只是一个逻辑错误，不应该导致段错误。

2. 看来您遇到了堆栈溢出。

   我们来做个简单的计算。对于 10000 * 10000 的矩阵和 10000 的字长，如果您在矩阵的左上角开始调用 Find()，则可能有三个方向。在最坏的情况下，Find() 将遍历大约 10000*3 个元素。请注意，在 Func() 中有 3 个字符串实例(32 位 VC2013 中的 sizeof(string) == 24)，以及各种整数。单个帧的大小很容易超过 100 字节。由于您使用的是递归调用，这可能导致堆栈使用至少 10000 * 3 * 100 = 3000000bytes = 大约。 3M。

   这个数字不是很大，但足以导致堆栈溢出，因为 Windows 的默认堆栈大小为 1M。 ( http://msdn.microsoft.com/en-us/library/8cxs58a6.aspx )

改进建议

这是我用来解决这类矩阵遍历问题的模式。

首先，定义一个常量数组来保存移动的偏移量 (Moore neighborhood):

const int delta[8][2] = {
    { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 },
    { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }
};

其次，使用单个 for 来检查所有方向:

int initial_x = .., initial_y = ..;
for (int dir = 0; dir < 8; dir++) {
    for (int count = 0; count < WORD_LENGTH; count++) {
        int current_x = initial_x + delta[dir][0] * count;
        int current_y = initial_y + delta[dir][1] * count;
        if (IS_INVALID(current_x, current_y)) {
            break;
        }
    }
}

最后，插入各种代码和标志来完成程序。

另一个提示:您可以使用char 类型来获取和比较字符串中的单个字符(使用word[idx] 来获取idxword 的第一个字符)。这可能比使用 substr 快得多。