구글의 세분화 오류

나는 무차별 접근법에서의 문제를 푸는 중이다. 입력은 다음과 같습니다.구글의 세분화 오류

문자열로 표시되는 격자 행렬입니다 (예 : '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의 : 단어가 유효 할 때 올바른 실행 ("ESP"boogle.contains ("PESA"))

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)

출처

2013-10-27 Dzung Nguyen

조건 목록 앞에 cout << grid_index-1-matsize << endl;을 표시하려고하면. grid_index은 서명이 없으므로 버퍼 언더 플로가 발생합니다.

따라서 이 참이면 grid_index은 grid.length() 이상입니다.

당신은 내가 ++ g에 -Wall 켜

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

출처

2013-10-27 23:19:51 Masadow

사실 grid_index는 행렬에 대한 것입니다. 변수 수는 단어에 대한 것이고 나는 여기에서 경계를 확인합니다 : grid_index

@DzungNguyen 그래, 시간이 걸렸고 코드를주의 깊게 살펴 보았으니 지금 내 대답이 더 적합해야한다;) – Masadow

감사합니다. 많이, 나는 일주일 동안이 버그에 문제가있었습니다! –

당신은 서명과 서명되지 않은 산술 혼합된다. matsize은 int이고 grid_index은 unsigned int입니다. >0과의 비교는 결과가 항상 부호가 없으므로 부정적이지 않으므로 작동하지 않습니다.

btw, 부호가있는/부호없는 불일치를 수정 한 후에 >=0이 필요합니다.

출처

2013-10-27 23:16:26

로 기능 checkqueue의 서명을 변경해야하고, 그것에 대해 경고를 표시하지 않습니다. 나는 서명하지 않아도되지만 도움이되지 않는다. 문제는 다음 재귀를 찾을 수 없을 때 (유효한 이동 없음) 세그먼트 화 문제가있는 경우입니다. –

'(unsigned int)> = 0'은 항상 참이므로 의미가 없으므로'> = 0'이면 경고가 일어날 것이라고 생각합니다. '(unsigned int)> 0'은 0 일 경우 true 일 수 있으므로 경고를받지 못합니다. –

구글의 세분화 오류

답변

관련 문제