매트릭스에서 한 지점에서 다른 지점으로 탈출 경로를 찾는 방법은 무엇입니까?

Question

이것은 숙제가 아닙니다. 그것은 단지 연습 문제입니다.

주어진 행렬에서 (0,0)에서 (N, N)까지 가능한 이탈 경로 수를 찾습니다. 대각선으로 이동할 수 없습니다.

'0'은 열린 셀을 나타내고 '1'은 차단 된 셀을 나타냅니다. 나는 (0,0)에서 여행을 시작했고 (N, N)에 도달해야했다.

입력 형식

첫 번째 행은 행렬의 사이즈를 나타내는 하나의 홀수의 양의 정수, T (= 85을 <)이다. T 행은 각각 '0'또는 '1'인 T 공백으로 분리 된 숫자를 포함합니다. (N, N)에

출력 형식

출력 내가 (0,0)에서 탈출 할 수있는 방법의 수.

샘플 입력

7 
0 0 1 0 0 1 0 
1 0 1 1 0 0 0 
0 0 0 0 1 0 1 
1 0 1 0 0 0 0 
1 0 1 1 0 1 0 
1 0 0 0 0 1 0 
1 1 1 1 0 0 0 

샘플 출력

4 

내 솔루션에 따르면 내가 네 방향을 촬영 한 - 오른쪽 (R), 왼쪽 (L), 최대 (U) , 아래 (d).

문제는 잘못된 대답 또는 stackoverflow 오류가 발생하는 것입니다. 없어진 물건 있어요?

그리고이 질문에 대한 최적의 해결책입니까?

내 솔루션 (자바)

import java.io.BufferedReader; 
import java.io.InputStreamReader; 

class testclass { 
int no_of_escapes = 0 ; 
int[][] arr; 
int matrixlength; 
public static void main(String[] args) throws Exception 
{ 

    testclass obj = new testclass(); 
    obj.checkpaths(0,0,""); 
    System.out.print(obj.no_of_escapes); 

}//main 

testclass() 
{ 
    try 
    { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    matrixlength =Integer.parseInt(br.readLine());  
    arr = new int[matrixlength][matrixlength]; 
    for(int k = 0; k < matrixlength; k++){ 

     String str = br.readLine(); 
     int count = 0; 
     for(int j=0 ; j< ((2*matrixlength)-1); j++){ 
      int v = (int)str.charAt(j) - 48; 
      if(v == -16){} 
      else{ 
      arr[k][count] = v; 
      count++; 
      } 

     }//for j 

    }//for k 

} 
catch(Exception e){} 
} 

public void checkpaths(int m, int n,String direction){ 

    if((m == matrixlength -1) && (n == matrixlength-1)) 
    { 
     no_of_escapes = no_of_escapes +1; 
     return; 
    } 

    if(!direction.equals("l")) 
    { 
     if(m < matrixlength && n < matrixlength) 
      { 
       if((n+1) < matrixlength) 
        { 
         if(arr[m][n+1]==0) 
          { 
           checkpaths(m,n+1,"r"); 
          } 
        } 
      } 
    } 

    if(!direction.equals("u")) 
    { 
     if((m+1) < matrixlength) 
     { 
      if(arr[m+1][n]==0) 
      { 
      checkpaths(m+1,n,"d");     
      } 
     } 
    } 

    if(!direction.equals("r")) 
    { 
     if(m < matrixlength && n < matrixlength) 
      { 
       if((n+1) < matrixlength) 
        { 
         if(arr[m][n+1]==0) 
          { 
           checkpaths(m,n+1,"l"); 
          } 
        } 
      } 
    } 

    if(!direction.equals("d")) 
    { 
     if((m-1)>=0) 
     { 
      if(arr[m-1][n]==0) 
      { 
      checkpaths(m-1,n,"u");     
      } 

     } 

    } 


} 
}//class 

Answer 1

나는 아래의 코드에서와 같이, 당신은 이미 방문한 세포를 표시하는 논리 값의 두 번째 2 차원 배열을 유지하는 것입니다. 또한 코드 중복을 줄이기 위해 코드의 일부분을 단순화했습니다.

물론 arr으로 초기화 한 것처럼 visited을 생성자로 초기화해야하며 visited = new boolean[matrixLength][matrixLength]을 사용해야합니다.

int[][] arr; 
boolean[][] visited; 
final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 

public boolean isValid(int x, int y) { 
    return 0 <= x && x < matrixLength 
     && 0 <= y && y < matrixLength 
     && arr[x][y] == 0 
     && !visited[x][y]; 
} 


public void checkPaths(int x, int y) { 
    if (x == matrixLength-1 && y == matrixLength-1) { 
     no_of_escaped++; 
    } else { 
     for (int[] d : directions) { 
      if (isValid(x + d[0], y + d[1])) { 
       visited[x + d[0]][y + d[1]] = true; 
       checkPaths(x + d[0], y + d[1]); 
       visited[x + d[0]][y + d[1]] = false; 
      } 
     } 
    } 
}