/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 04 - 01
 * 
 * License: Creative Commons
 * 
 * Copyright by Mahsa Sadi
 * 
 *
 */

public class PathFinderV2 implements PathFinder {
	
	
	/**
	 * Problem: Find All Unique Paths
	 * 
	 * Description:
	 * 
	 * A robot is located at the top-left corner of a m x n grid.
	 * The robot can only move either down or right at any point in time. 
	 * The robot is trying to reach the bottom-right corner of the grid.
	 * How many possible unique paths are there?
	 * 
	 * 
	 * 
	 * Solution:
	 * 
	 * 1- Start from the destination cell and move upward over the diameter of the matrix. 
	 * 2- Count unique paths from the cell to destination.
	 * 3- Count unique paths from all the cells that are in the same row with the cell.
	 * 4- Count unique paths from all the cells that are in the same column with the cell.
	 *   
	 *    # unique paths from a cell to the destination 
	 *    = # unique paths from the right neighbor
	 *    + # unique path from the bottom neighbor.
	 *
	 * 5- Go the next cell on the diameter of the matrix.
	 * 
	 * 6-Return the # unique paths from cell [0][0] to the destination. 
	 * 
	 */

	int[][] numberOfUniquePathsFromNode;
	int numberOfRows;
	int numberOfColumns;

	
	
	@Override
	public int uniquePaths(int m, int n) 
	{
		numberOfUniquePathsFromNode = new int[m][n];
		numberOfRows = m;
		numberOfColumns = n;

		int x = numberOfRows - 1;
		int y = numberOfColumns - 1;

		while (x >= 0 && y >= 0) {
			for (int i = x; i >= 0; i--)
				countPathsFromNode(i, y);

			for (int j = y - 1; j >= 0; j--)
				countPathsFromNode(x, j);
			x--;
			y--;
		}

		return numberOfUniquePathsFromNode[0][0];
	}

	
	
	
	public void countPathsFromNode(int x, int y) 
	{

		if (x == numberOfRows - 1) {
			if (y == numberOfColumns - 1)
				numberOfUniquePathsFromNode[x][y] = 1;

			else
				numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x][y + 1];
		}

		else if (y == numberOfColumns - 1)
			numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x + 1][y];

		else
			numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x + 1][y]
					+ numberOfUniquePathsFromNode[x][y + 1];

	}

}