#K53252. Unique Grid Paths

    ID: 29490 Type: Default 1000ms 256MiB

Unique Grid Paths

Unique Grid Paths

You are given a grid with m rows and n columns. Starting from the top-left corner, your task is to find the number of distinct paths to reach the bottom-right corner, where you can only move either down or right at any step.

This problem can be solved using dynamic programming. If you denote dp[i][j] as the number of ways to reach cell (i, j), then the recurrence is given by:

dp[i][j]=dp[i1][j]+dp[i][j1]dp[i][j] = dp[i-1][j] + dp[i][j-1]

with the base cases:

  • For the first row: dp[0][j] = 1 for all j.
  • For the first column: dp[i][0] = 1 for all i.

Your program will read the grid dimensions from standard input and print the number of unique paths to standard output.

inputFormat

The input consists of two space-separated integers:

  • m: the number of rows in the grid.
  • n: the number of columns in the grid.

You should read the input from stdin.

outputFormat

Output a single integer representing the number of distinct paths from the top-left to the bottom-right corner of the grid. The result should be printed to stdout.

## sample
3 3
6