boogle中的分段錯誤

Question

我正試圖在蠻力方法中解決boogle問題。輸入是：

網格矩陣表示爲一個字符串，例如：'pesa' 該單詞也表示爲一個字符串'asa'。

我正在寫一個函數來檢查該單詞是否是矩陣中的合法單詞。

bool Boogle::contains(std::string grid, std::string word) const 
{ 
    bool* isvisited=new bool[grid.length()]; 
    for (unsigned int i=0; i<grid.length(); i++) 
    { 
     *(isvisited+i)=false; 
    } 

    for (unsigned int i=0; i<grid.length(); i++) 
    { 
     // Recursive approach 
     if (grid[i]==word[0]) 
      if (checkqueue(grid, word, isvisited, i, 0)) 
       return true;  
    } 
    return false; 
} 

bool Boogle::checkqueue(const string &grid, const string &word, bool* const &isvisited, unsigned int grid_index, unsigned int count) const 
{ 
    int matsize=int(sqrt(grid.length())); 
    cout<<"\nCurrently at the index "<<grid_index<<"\n"; 
    isvisited[grid_index]=true; 
    for (unsigned int i=0; i<grid.length(); i++) 
    { 
     cout <<isvisited[i]<<" "; 
    } 
    cout<<"\n"; 

    if (count==word.length()-1) 
    { 
     cout << " reach the end of word\n"; 
     return true; 
    } 
    else 
    { 
     count ++; 
     cout << "Recursive call on WORD: "<<word<<" " <<count<<" "<<word[count]<<"\n"; 

     // non diagonal 
     if ((grid_index<grid.length()) && (isvisited[grid_index+1]==false) && (grid[grid_index+1]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index+1, count); 

     else if ((grid_index>0)&& (isvisited[grid_index-1]==false) && (grid[grid_index-1]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index-1, count); 

     else if (((grid_index+matsize)<grid.length())&& (isvisited[grid_index+matsize]==false) && (grid[grid_index+matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index+1, count); 

     else if (((grid_index-matsize)<grid.length())&& (isvisited[grid_index-matsize]==false) && (grid[grid_index-matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index+1, count); 

     // diagonal 
     else if ((grid_index-1-matsize>0)&& (isvisited[grid_index-1-matsize]==false) && (grid[grid_index-1-matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index-1-matsize, count); 

     else if ((grid_index+1-matsize>0) && (isvisited[grid_index+1-matsize]==false) && (grid[grid_index+1-matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index+1-matsize, count); 

     else if ((grid_index+1+matsize<grid.length())&& (isvisited[grid_index+1+matsize]==false) && (grid[grid_index+1+matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index+1+matsize, count); 

     else if ((grid_index-1+matsize<grid.length())&& (isvisited[grid_index-1+matsize]==false) && (grid[grid_index-1+matsize]==word[count])) 
      return checkqueue(grid, word, isvisited, grid_index-1+matsize, count); 
     else 
     { 
      // cout<<"No possible neighbor\n"; 
      return false; 
     } 

    } 
} 

如果我運行boogle.contains（「pesa」，「as」）它很好。但是，如果這是一個非法的詞，如「asa」，它會返回分段錯誤。這是從哪裏來的？

./Boogle.exe 
. 
Currently at the index 3 
0 0 0 1 
Recursive call on WORD: asa 1 s 

Currently at the index 2 
0 0 1 1 
Recursive call on WORD: asa 2 a 
Segmentation fault: 11 

P/S：這是正確的運行這個詞的時候是有效的（boogle.contains（ 「PESA」， 「ESP」））

Currently at the index 1 
0 1 0 0 
Recursive call on WORD: esp 1 s 

Currently at the index 2 
0 1 1 0 
Recursive call on WORD: esp 2 p 

Currently at the index 3 
0 1 1 1 
reach the end of word 



OK (1 tests) 

Answer 1

如果您嘗試在條件列表之前顯示cout << grid_index-1-matsize << endl;。由於grid_index未簽名，您將看到發生緩衝區下溢。

因此，您的條件(grid_index-matsize)<grid.length()爲真，因爲grid_index比grid.length()要好。

你必須改變功能checkqueue的簽名改成

bool Boogle::checkqueue(const string &grid, const string &word, bool* const &isvisited, int grid_index, unsigned int count) const 

Answer 2

你混合符號和無符號運算。 matsize是int和grid_index是unsigned int。您與>0的比較不起作用，因爲結果始終未簽名，因此從不消極。

順便說一句，你可能想要>=0修復簽署/未簽名的不匹配。