The grid is big enough that it is not possible for us to merely try all possible paths.

We simply care about how many ways there are to get to a given square though. Let $f(x,y)$ be the number of ways there are to get to row $x$ and column $y$. Note that $f(x,y)$ is simply the sum of all $f(i,j)$ where $i < x$, $j < y$, and the numbers in those squares don't match. This gives us an $O(R^2 C^2)$ algorithm, which is fast enough for our purposes.

Here is my Java code that implements this, with the only difference being that it computes the DP in the reverse direction.

import java.io.*; import java.util.*; public class barnjump { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new FileReader("barnjump.in")); PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("barnjump.out"))); StringTokenizer st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int[][] grid = new int[r][c]; for(int i = 0; i < r; i++) { st = new StringTokenizer(br.readLine()); for(int j = 0; j < c; j++) { grid[i][j] = Integer.parseInt(st.nextToken()); } } final int MOD = 1000000007; int[][] dp = new int[r][c]; dp[0][0] = 1; for(int i = 0; i < r; i++) { for(int j = 0; j < c; j++) { for(int k = i+1; k < r; k++) { for(int l = j+1; l < c; l++) { if(grid[i][j] != grid[k][l]) { dp[k][l] += dp[i][j]; dp[k][l] %= MOD; } } } } } pw.println(dp[r-1][c-1]); pw.close(); } }