왼쪽 상단에서 오른쪽 하단까지의 주법 수량(중간에 장애가 있음)

3331 단어 동적 기획
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as1and0respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is2.
Note: m and n will be at most 100.
 
package leetcode;
public class Unique_paths_ii {      public static void main(String[] args) {          int [][]a = {{0,1,0,0,0},{1,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};         System.out.println(uniquePathsWithObstacles(a)); public static int unique Paths With Obstacles(int[][] [] obstacle Grid) {int m = obstacle Grid.length;//행 수 int n = obstacle Grid[0].length;//열 수 if (obstacle Grid[0][0] = = 1 | | obstacle Grid[m-1] [n-1] = 1){return 0;//시작점이나 끝점에 장애가 있으면 결과는 0} for(int i = 0; i < m; i++) {if(obstacleGrid[i][0]== 1) {//장애가 있으면 -100 obstacleGrid[i][0] = -100으로 설정합니다.else if(i>=1 &obstacle Grid[i-1][0]==-100) {//첫 번째 열의 위쪽에 장애가 있으면 이 열이 통과할 수 없기 때문에 모두 -100 obstacle Grid[i][0] = -100으로 설정합니다.else {obstacleGrid[i][0] = 1;//무장애 설정이 1이면 실행 가능} for(int j = 1; j < n; j++) {if(obstacleGrid[0] [j] = 1) {obstacleGrid[0] [j] = - 100;//장애가 있으면 - 100}else if(j>=1 &obstacleGrid[0][j-1]==-100) {//첫 번째 줄의 왼쪽에 장애가 있으면 이 줄을 모두 통과할 수 없기 때문에 모두 -100 obstacleGrid[0]로 설정[j] = -100;else {obstacleGrid[0] [j] = 1;//무장애 설정이 1이면 실행 가능} for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid [i] [j] = 1) {obstacleGrid [i] [j] = -100;//장애가 있으면 -100 continue로 설정합니다.else if(obstacle Grid[i-1] [j]===-100 &obstacle Grid[i][j-1]==-100) {obstacle Grid[i][j]=-100;/왼쪽과 위쪽에 모두 장애가 있으면 이 위치를 통과할 수 없으며 장애가 있는 것과 같습니다. -100}else if(obstacle Grid[i-1][j]=-100 &obstacle Grid[j][i][j]][j]] [j-100][i][j] = obstacleGrid[i][j-1];//위쪽에 장애가 있으면 왼쪽으로 통과하고,왼쪽 위치에 저장된 주법 수량을 계승한다}else if(obstacleGrid[i-1][j]!=-100 & & obstacleGrid[i][j-1]==-100) {obstacleGrid[i][j] =obstacleGrid[i-1] [j];//왼쪽에 장애가 있으면 위에서 통과하고 위쪽 위치에 저장된 주법 수량을 계승한다}else {obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1];//왼쪽과 위쪽이 모두 장애가 없으면 이 위치를 통과할 수 있으며 두 방향의 주법 수량을 더한 후 계승할 수 있습니다}}} if (obstacleGrid [m-1] [n-1] ==-100) {//마지막에 어떤 주법도 계승하지 않으면 0 return 0으로 되돌아갈 수 있습니다.        }else {             return obstacleGrid[m-1][n-1]; }//다음은 뉴커넷의 최우선 해법/*public class Solution {public int unique Paths With Obstacles(int[] [] obstacle Grid) {int m = obstacle Grid.length;//취득 행수if(m==0 | | obstacle Grid[0] = = = 1)//행수가 0이거나 기점에 장애가 있으면 0 return 0으로 바로 반환; int n = obstacle Grid[0].length;//열수 int[][] steps = new int[m][n] 얻기;//같은 크기의 2차원 그룹 steps[0][0] = 1;//이때 기점은 장애가 있는 상황을 배제했기 때문에 직접 1for(int i=1;i if(obstacleGrid[0][i]=1)steps[0][i]=0을 부여한다.            else                 steps[0][i] = steps[0][i-1];         }         for(int i=1; i             if(obstacleGrid[i][0] == 1)                 steps[i][0] = 0;             else                 steps[i][0] = steps[i-1][0]; for(int i=1;i for(int j=1;j if(obstacleGrid[i][j]==1)//여기에 장애가 있으면 0을 부여하고 이 위치를 나타내는 주법 수는 0 steps[i][j]=0이다.                else                     steps[i][j] = steps[i-1][j] + steps[i][j-1];//여기에 장애가 없으면 왼쪽과 위쪽의 주법 수의와}return steps[m-1][n-1];//마지막 반환}} */

좋은 웹페이지 즐겨찾기