2015 Feb Silver Problem 2 Cow Hopscotch (Silver)

Official Problem Statement

Cow Hopscotch (Silver)

Problem

The problem introduces a hopscotch grid of size R × C. Each square in the grid has a positive integer in it. The rules of this cow hopscotch game are as follows:

• The cow starts in the top-left square and wants to reach the bottom-right square.
• From a square in row r and column c, the cow can only jump to a square in row r' and column c' if 1 ≤ r < r' ≤ R and 1 ≤ c < c' ≤ C.
• Moreover, the integers in the starting and ending squares of the jump must be different.

The cow wishes to know the total number of different ways she can play the game.

Solution

The key observation is that the number of ways to reach a particular square is the sum of the ways to reach all the squares that can jump to it. A 2D DP array can be used to store the number of ways to reach each square.

For a square in row r and column c, iterate over all the previous squares (in rows 1 through r-1 and columns 1 through c-1). If the previous square has a different value, add the number of ways to reach that square to the number of ways to reach the current square.

The time complexity of this solution is O(R^2*C^2), which is feasible because R and C are both at most 100.

Code

C++

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

using namespace std;

const int MOD = 1000000007;

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

    int rows, cols;
    fin >> rows >> cols;

    vector<vector<int>> grid(rows, vector<int>(cols));
    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            fin >> grid[row][col];
        }
    }

    vector<vector<int>> dp(rows, vector<int>(cols, 0));
    dp[0][0] = 1;

    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            for (int nextRow = row + 1; nextRow < rows; ++nextRow) {
                for (int nextCol = col + 1; nextCol < cols; ++nextCol) {
                    if (grid[row][col] != grid[nextRow][nextCol]) {
                        dp[nextRow][nextCol] += dp[row][col];
                        dp[nextRow][nextCol] %= MOD;
                    }
                }
            }
        }
    }

    fout << dp[rows - 1][cols - 1] << endl;

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class BarnJump {
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("barnjump.in"));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("barnjump.out")));

        StringTokenizer st = new StringTokenizer(reader.readLine());
        int rows = Integer.parseInt(st.nextToken());
        int cols = Integer.parseInt(st.nextToken());

        int[][] grid = new int[rows][cols];
        for(int row = 0; row < rows; row++) {
            st = new StringTokenizer(reader.readLine());
            for(int col = 0; col < cols; col++) {
                grid[row][col] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[rows][cols];
        dp[0][0] = 1;

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                for(int nextRow = row + 1; nextRow < rows; nextRow++) {
                    for(int nextCol = col + 1; nextCol < cols; nextCol++) {
                        if(grid[row][col] != grid[nextRow][nextCol]) {
                            dp[nextRow][nextCol] += dp[row][col];
                            dp[nextRow][nextCol] %= MOD;
                        }
                    }
                }
            }
        }

        writer.println(dp[rows - 1][cols - 1]);
        writer.close();
    }
}

Python

MOD = 1000000007

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

    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1

    for row in range(rows):
        for col in range(cols):
            for next_row in range(row + 1, rows):
                for next_col in range(col + 1, cols):
                    if grid[row][col] != grid[next_row][next_col]:
                        dp[next_row][next_col] += dp[row][col]
                        dp[next_row][next_col] %= MOD

    with open('barnjump.out', 'w') as fout:
        fout.write(f"{dp[rows - 1][cols - 1]}\n")

if __name__ == "__main__":
    main()