2D 행렬의 패턴 검색

Question

이것은 인터뷰 질문입니다

2 차원 배열로 문자열을 찾아야합니다. 입력은 2 차원 배열의 문자와 주어진 문자열을 포함합니다. 8 가지 방향 중 하나로 이동할 수 있습니다. string은 문자열이 완전히 발견되면 문자열의 첫 번째 문자 위치를 포함하고, 그렇지 않으면 -1을 반환합니다. 가능한 경우 복수 응답 중 하나가 허용됩니다. 예를 들어

, 입력 :

b t g 
p a d 
r k j 

String: rat 
Output: (2,0) 

내가 도와주세요

5 5 
    A C P R C 
    X S O P C 
    V O V N I 
    W G F M N 
    Q A T I T 

    MICROSOFT 

이 있지만 점점 잘못된 출력을 시도

#include<iostream> 
#include<string> 
using namespace std; 
bool isInside(int x,int y,int m,int n) 
{ 
    if(x>=0&&x<m&&y>=0&&y<n)return true; 
    return false; 
} 
void findString(char mat[10][10],int m,int n,string str) 
{ 
    int i,j; 

    for(i=0;i<m;i++) 
     for(j=0;j<n;j++) 
    { 
     int k=0,x=i,y=j; 
     bool flag=true; 
     if(mat[i][j]==str[k]) 
     { 
      while(flag&&k<str.size()) 
      { 
       int x1=x-1,x2=x+1,y1=y-1,y2=y+1; 
       if(isInside(x1,y1,m,n)&&mat[x1][y1]==str[k]) 
        { 
         x=x1; y=y1; k++; 
        } 
       else if(isInside(x1,y,m,n)&&mat[x1][y]==str[k]) 
        { 
         x=x1; y=y; k++; 
        } 
       else if(isInside(x1,y2,m,n)&&mat[x1][y2]==str[k]) 
        { 
         x=x1; y=y2; k++; 
        } 
       else if(isInside(x,y1,m,n)&&mat[x][y1]==str[k]) 
        { 
         x=x; y=y1; k++; 
        } 
       else if(isInside(x,y2,m,n)&&mat[x][y2]==str[k]) 
        { 
         x=x; y=y2; k++; 
        } 
       else if(isInside(x2,y1,m,n)&&mat[x2][y1]==str[k]) 
        { 
         x=x2; y=y1; k++; 
        } 
       else if(isInside(x2,y,m,n)&&mat[x2][y]==str[k]) 
        { 
         x=x2; y=y; k++; 
        } 
       else if(isInside(x2,y2,m,n)&&mat[x2][y2]==str[k]) 
        { 
         x=x2; y=y2; k++; 
        } 
       else flag=false; 
      } 
      if(flag==true) 
      { 
       cout<<endl<<"\("<<i<<","<<j<<")"<<endl; 
       return; 
      } 
     } 
    } 
    cout<<endl<<"-1"<<endl; 
    return; 
} 
int main() 
{ 
    int i,j,n,m; 
    char mat[10][10]; 
    string str; 
    cout<<"enter the dimention of the matrix: "; 
    cin>>m>>n; 
    cout<<endl<<"enter the char matrix:"<<endl; 
    for(i=0;i<m;i++) 
     for(j=0;j<n;j++) 
     cin>>mat[i][j]; 
    cout<<endl<<"enter the test string: "; 
    cin>>str; 
    findString(mat,m,n,str); 
    return 0; 
} 

Answer 1

검색에서 주어진 위치에서 때문에 완료되지 당신은 하나의 유효한 이웃만을 시도합니다.

예를 들어, M부터 시작하여 바닥이 I 인 경우 검색이 중지됩니다. 오른쪽 상단의 I도 시도해야하며 재귀 적 솔루션이 필요합니다.

귀하의 솔루션도 동일한 문자로 두 번 통과하지 못하지만, 합법적인지 여부는 확실하지 않습니다.

는 의사 코드 :

Try(i, j, Suffix): 
    if i < 0 or i >= m or j < 0 or j >= n: 
    # No such position 
    return 

    if Mat[i][j] == Suffix[0]: 
    if len(Suffix) == 1: 
     # The whole string was matched 
     print "Found !" 
     return 

    # Mark the position (optional) 
    Mat[i][j]= uppercase(Mat[i][j]) 

    # Try all 8 neighbors 
    Try(i+1, j, Suffix[1:]) 
    Try(i+1, j+1, Suffix[1:]) 
    Try(i, j+1, Suffix[1:]) 
    ... 

    # Unmark the position (optional) 
    Mat[i][j]= lowercase(Mat[i][j]) 

당신은 내가 이해

for i in range(m): 
    for j in range(n): 
    Try(i, j, String)