2015 Feb Bronze Problem 3 Cow Hopscotch (Bronze)

Official Problem Statement

Cow Hopscotch (Bronze)

Problem

In this problem, Bessie the cow is playing a variant of the classic game "hopscotch" on a grid of squares (R x C, where R is the number of rows and C is the number of columns). Starting from the top-left square, Bessie hops in a two-dimensional way, moving downwards towards the bottom-right square. Each move Bessie makes must be strictly downwards and to the right.

Bessie wants to make the game more interesting, so she decides that she will only make a hop to a square if it has a different number than the square she is currently standing on. She wonders in how many ways she can reach the bottom-right square.

Each of the R*C squares has a number in the range of 1…K, where K (1 ≤ K ≤ 100) is the total number of different numbers a square can have. The input guarantees that Bessie can reach the bottom-right square.

Write a program to determine the number of ways Bessie can reach the bottom-right square.

Solution

This problem is a classic example of dynamic programming. The solution to the problem involves creating a 2D DP table the same size as the grid. For each cell in the grid, you count the number of ways Bessie can reach it by adding up the number of ways to reach each cell from which it can be reached (i.e., cells that are strictly to its upper and left and contain a different number).

The value in the bottom-right cell will represent the total number of ways Bessie can reach the destination.

The computational complexity of this solution is O(R²*C²), which is feasible given the problem constraints.

It should be noted that the result may be too large to fit into a 32-bit integer and, thus, a larger data type should be used for the calculations. Additionally, to avoid overflows, you should perform modulo operations with a large prime number (like 10^9+7) as often as possible.

Code

C++

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int main() {
    ifstream fin("barnjump.in");
    ofstream fout("barnjump.out");

    int r, c;
    fin >> r >> c;
    vector<vector<int>> grid(r, vector<int>(c, 0));
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            fin >> grid[i][j];
        }
    }

    vector<vector<long long>> dp(r, vector<long long>(c, 0));
    dp[0][0] = 1;
    const int MOD = 1e9+7;

    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;
                    }
                }
            }
        }
    }

    fout << dp[r-1][c-1] << endl;
    return 0;
}

Java

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());
      }
    }

    int[][] dp = new int[r][c];
    dp[0][0] = 1;
    final int MOD = 1000000007;

    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();
  }
}

Python

def count_paths(grid, x, y):
    if x == len(grid) - 1 and y == len(grid[0]) - 1:
        # We've reached the end, so this path is valid.
        return 1
    # Try all possible next moves and sum the total number of paths.
    count = 0
    for i in range(x + 1, len(grid)):
        for j in range(y + 1, len(grid[0])):
            if grid[i][j] != grid[x][y]:
                count += count_paths(grid, i, j)
    return count


def main():
    with open('barnjump.in', 'r') as fin:
        r, c = map(int, fin.readline().split())
        grid = [list(map(int, fin.readline().split())) for _ in range(r)]

    with open('barnjump.out', 'w') as fout:
        fout.write(str(count_paths(grid, 0, 0)))


if __name__ == "__main__":
    main()