Упражнения на Java: поиск возможных уникальных путей с учетом некоторых препятствий, от верхнего левого угла до нижнего правого угла указанной сетки

Java Basic: упражнение 137 с решением

Напишите программу на Java, чтобы найти возможные уникальные пути с учетом некоторых препятствий, от верхнего левого угла до правого нижнего угла данной сетки (mxn).

Примечание: Вы можете двигаться вниз или вправо в любой момент времени, и препятствие и пустое пространство помечаются как 1 и 0 соответственно в сетке. Пример сетки:
int [] [] tactcle_Grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0},
};

Пример решения:

Java-код:

public class Solution {
    public static int uniquePaths_With_obstacle_Grid(int[][] obstacle_Grid) {
		int m = obstacle_Grid.length;
		if (m <= 0) {
			return 0;
		}
		int n = obstacle_Grid[0].length;
		if (n <= 0) {
			return 0;
		}
		int[][] dp = new int[m + 1][n + 1];
		dp[m][n - 1] = 1;
		for (int i = m - 1; i >= 0; --i) {
			for (int j = n - 1; j >= 0; --j) {
				dp[i][j] = (obstacle_Grid[i][j] == 0) ? dp[i + 1][j] + dp[i][j + 1] : 0;
			}
		}
		return dp[0][0];
	}
    
  public static void main(String[] args) {
		int[][] obstacle_Grid ={
                              {0, 0, 0}, 
                              {0, 1, 0}, 
                              {0, 0, 0}, 
                              };
		System.out.println("Unique paths from top-left corner to bottom-right corner of the said grid (considering some obstacles): "+uniquePaths_With_obstacle_Grid(obstacle_Grid));
	}		
}

Пример вывода:

 Уникальные пути из верхнего левого угла в правый нижний угол указанной сетки (с учетом некоторых препятствий): 2 с

Блок - схема:

Редактор кода Java:

Компания: Bloomberg

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на Java, чтобы найти возможные уникальные пути от верхнего левого угла до нижнего правого угла данной сетки (mxn).
Далее: Напишите программу на Java, чтобы найти все самое длинное слово в данном словаре.