OA consisted of two questions

1. Colorful Path Maze

You are given a 2D grid of size N × M, where each cell contains a color represented by an integer.

Your task is to count the number of distinct paths from the top-left corner (0, 0) to the bottom-right corner (N-1, M-1) such that:

You can move only right or down at each step. You cannot visit a color that has already appeared in the current path. In other words, no two cells in the same path can have the same color.

Use backtracking to explore all possible paths and count the number of paths that satisfy the color-uniqueness condition. The function should return the number of valid colorful paths from (0, 0) to (N-1, M-1).

Parameters N — An integer representing the number of rows in the grid. M — An integer representing the number of columns in the grid. grid — A 2D array of integers of size N × M, where each integer represents a color. Return Value

Return an integer representing the number of valid colorful paths from (0, 0) to (N-1, M-1).

Input Format

The input consists of:

The first line containing a single integer N. The second line containing a single integer M. The next N lines each contain M space-separated integers representing the colors in the grid. Output Format

Print a single integer representing the number of valid colorful paths.

Constraints 1 ≤ N, M ≤ 10 0 ≤ grid[i][j] ≤ 100 Sample Input 3 3 1 2 3 4 5 6 7 8 9 Sample Output 6

2. Problem on Binary Search on answer