문자 행렬에서 문자열 경로를 찾는 방법은 무엇입니까?

Question

문자 행렬에 문자열 경로가 있는지 여부를 확인하는 함수를 구현하는 방법은 무엇입니까? 행렬에서 왼쪽, 오른쪽, 위아래로 이동하고 이동을위한 셀로 이동합니다.

경로는 행렬의 항목에서 시작할 수 있습니다. 셀이 경로의 문자열 문자로 가득 차면 다른 문자가 다시 차지할 수 없습니다.

원하는 경우이 문제를 푸시 코드 (Psuedocode)로 해결 하시겠습니까? 나의 초기 생각은 이것을 그래프 문제로 해석하고 행렬 위치를 그래프의 정점으로 해석하는 것이다.

Answer 1

편집 : 여기

는 하스켈 솔루션 (I 함수 여기 행렬을 교체하고 있습니다 :

class Pair { 
    public Pair(int x, int y) { this.x = x; this.y = y; } 
    public int x; 
    public int y; 
}; 

class Main { 
    static Vector<Pair> singleton(Pair p) { 
     Vector<Pair> v = new Vector<Pair>(); 
     v.insert(p); 
     return v; 
    } 

    static void f(String str, int [][]matrix, int width, int height) { 
     Vector<Vector<Pair>> v = new Vector<Vector<Pair>>(); 
     for (int i = 0; i < height; ++i) 
      for (int j = 0; j < width; ++j) 
       try(i, j, str, matrix, width, height, v); 
    } 

    static void try(int i, int j, String str, int [][]matrix, int width, int height, Vector<Vector<Pair>> v) { 
     int old_v_size = v.length; 
     if (i < 0 || i >= height || j < 0 || j >= width) return; 
     if (str.length == 1) v.insert(singleton(new Pair(i,j)); 
     try(i+1,j,str.substr(1),matrix,width,height,v); 
     try(i-1,j,str.substr(1),matrix,width,height,v); 
     try(i,j+1,str.substr(1),matrix,width,height,v); 
     try(i,j-1,str.substr(1),matrix,width,height,v); 
     for (int k = old_v_size; k < v.length; ++k) v[k].insert(new Pair(i,j)); 
    } 

} 

올드 아래 코드는 다음과 느린 반 자바 반 의사 코드 버전을 추가 두 개의 정수를 가져 와서 행렬의 값을 반환합니다). 함수 f는 문자열, 행렬 함수, 너비 및 높이를 받아들이고 각 가능한 솔루션에 대한 튜플 목록 목록을 반환합니다.

f str matrix width height = 
    concat [try i j str matrix width height | i <- [0..width-1], j <- [0..height-1] ] 


try i j (c:cs) matrix width height | i < 0 || 
            i >= height || 
            j < 0 || 
            j >= width || 
            matrix i j /= c = [] 
try i j [c] matrix width height = [(i,j)] 
try i j (c:cs) matrix width height = 
    concat [map ((i,j):) $ try (i+1) j cs matrix width height, 
      map ((i,j):) $ try (i-1) j cs matrix width height, 
      map (c:) $ try i (j+1) cs matrix width height, 
      map (c:) $ try i (j-1) cs matrix width height] 

당신은 다른 언어를 지정하세요 원한다면 나는 다른 해결책 자바에 대한

Answer 2

public class MatrixSearch { 

    public static void main(String[] args) { 

     String[] find = {"M", "I", "C", "R", "O", "S", "O", "F", "T"}; 

     String[][] matrix = { 
      {"A", "C", "P", "R", "C"}, 
      {"M", "S", "O", "P", "C"}, 
      {"I", "O", "V", "N", "I"}, 
      {"C", "G", "F", "M", "N"}, 
      {"Q", "A", "T", "I", "T"} 
     }; 
     // printing matrix... 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       System.out.print(matrix[i][j]); 
      } 
      System.out.println(""); 
     } 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       if (matrix[i][j].equals(find[0])) { 
        System.out.println(matrix[i][j]); 
        boolean found = recursiveMatrixFind(matrix, i, j, matrix.length, matrix.length, find, 1);      
        System.out.println(found); 
       } 
      } 
     } 
    } 

    public static boolean recursiveMatrixFind(String[][] matrix, int row, int column, int rowLength, int columnLength, String[] find, int k) { 

     if (k == find.length) { 
      return true; 
     } 

     for (int neighbourRow = row - 1; neighbourRow <= row + 1; neighbourRow++) { 
      if (neighbourRow >= 0 && neighbourRow < rowLength) { 
       for (int neighbourColumn = column - 1; neighbourColumn <= column + 1; neighbourColumn++) { 
        if (neighbourColumn >= 0 && neighbourColumn < columnLength) { 
         if ((!(neighbourRow == row && neighbourColumn == column))) { 
          if (matrix[neighbourRow][neighbourColumn].equals(find[k])) { 
           System.out.println(matrix[neighbourRow][neighbourColumn]); 
           boolean found = recursiveMatrixFind(matrix, neighbourRow, neighbourColumn, rowLength, columnLength, find, ++k); 
           if (found) { 
            return true; 
           } else { 
            continue; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     return false; 
    } 
}