2015 Open Bronze Problem 4 Palindromic Paths (Bronze)

Official Problem Statement

Palindromic Paths (Bronze)

Problem

The problem titled 'Palindromic Paths' in the 2015 USACO Open Bronze contest is as follows:

Bessie is standing at the top-left corner of a pasture grid that has N (1 ≤ N ≤ 15) rows and M (1 ≤ M ≤ 15) columns, denoted as (1,1). She can only move down or to the right. Her goal is to reach the bottom-right corner of the grid, (N,M), in such a way that the sequence of numbers in the cells she passes through forms a palindrome.

Every cell in the grid contains a digit from 0 to 9, inclusive. A sequence forms a palindrome if it reads the same forwards and backwards. For instance, the sequences "12321" and "22" are palindromes, but "123" and "11" are not.

Find the number of different paths Bessie can take from (1,1) to (N,M) such that the sequence of numbers in the cells along the path forms a palindrome.

Solution

The solution to the problem involves using dynamic programming and depth-first search.

The key insight to solve this problem is that any palindromic path from (1,1) to (N,M) must pass through the center of the grid. So, we start from (1,1) and (N,M), and move towards the center of the grid simultaneously. This way, we ensure that the sequence of numbers in the cells we pass through is always a palindrome.

We use a 4-dimensional array to store our dynamic programming state. The first two dimensions represent the current positions (r1,c1) and (r2,c2) that we are at while moving from (1,1) and (N,M) respectively. The last dimension represents the distance that we have moved from (1,1) towards the center of the grid.

For each state, we check if the numbers at (r1,c1) and (r2,c2) are the same. If they are not, we cannot continue along this path because it would not form a palindrome. If they are the same, we recursively consider all possible ways to move from (r1,c1) and (r2,c2) towards the center of the grid, and add up the number of palindromic paths.

Finally, we return the total number of palindromic paths from the initial state (1,1) and (N,M).

The time complexity of this solution is O(N^2 * M^2) because for each state, we consider four possible next states, and there are N^2 * M^2 possible states.

Code

C++

#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#include <algorithm>

using namespace std;

int n;
vector<set<string>> rows1, rows2;

void dfs(vector<vector<char>>& grid, int x, int y, vector<set<string>>& sets, string curr) {
    if(x + y == n-1) {
        sets[x].insert(curr + grid[x][y]);
    }
    else {
        dfs(grid, x+1, y, sets, curr + grid[x][y]);
        dfs(grid, x, y+1, sets, curr + grid[x][y]);
    }
}

void transpose(vector<vector<char>>& grid) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i + j >= n-1) continue;
            swap(grid[i][j], grid[n-1-j][n-1-i]);
        }
    }
}

int main() {
    ifstream in("palpath.in");
    ofstream out("palpath.out");

    in >> n;
    vector<vector<char>> grid(n, vector<char>(n));
    rows1.resize(n);
    rows2.resize(n);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            in >> grid[i][j];
        }
    }

    dfs(grid, 0, 0, rows1, "");
    transpose(grid);
    dfs(grid, 0, 0, rows2, "");

    set<string> ans;
    for(int a = 0; a < n; a++) {
        for(string s: rows1[a]) {
            if(rows2[a].find(s) != rows2[a].end()) {
                ans.insert(s);
            }
        }
    }

    out << ans.size() << "\n";

    return 0;
}

Java

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

public class PalpathB {
    static int n;
    static Set<String>[] rows1, rows2;

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

        n = Integer.parseInt(br.readLine());
        char[][] grid = new char[n][n];

        // Initialize sets for storing paths from the corners to each diagonal
        rows1 = new HashSet[n];
        rows2 = new HashSet[n];
        for(int a = 0; a < n; a++) {
            rows1[a] = new HashSet<String>();
            rows2[a] = new HashSet<String>();
        }

        // Read the grid
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < n; j++) {
                grid[i][j] = s.charAt(j);
            }
        }

        // Find all possible paths from the corners to each diagonal
        dfs(grid, 0, 0, rows1, "");
        transpose(grid);
        dfs(grid, 0, 0, rows2, "");

        // Find the paths that can be generated from both corners
        Set<String> ans = new HashSet<String>();
        for(int a = 0; a < n; a++) {
            for(String s: rows1[a]) {
                if(rows2[a].contains(s)) {
                    ans.add(s);
                }
            }
        }

        pw.println(ans.size());
        pw.close();
    }

    // Depth-first search to find all paths from a corner to each diagonal
    public static void dfs(char[][] grid, int x, int y, Set<String>[] sets, String curr) {
        if(x + y == n-1) {
            sets[x].add(curr + grid[x][y]);
        } else {
            dfs(grid, x+1, y, sets, curr + grid[x][y]);
            dfs(grid, x, y+1, sets, curr + grid[x][y]);
        }
    }

    // Transpose the grid to reuse the dfs function for the bottom-right corner
    public static void transpose(char[][] grid) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i + j >= n-1) continue;
                char temp = grid[i][j];
                grid[i][j] = grid[n-1-j][n-1-i];
                grid[n-1-j][n-1-i] = temp;
            }
        }
    }
}

Python

from collections import defaultdict

def dfs(grid, x, y, sets, curr):
    if x + y == n - 1:
        sets[x].add(curr + grid[x][y])
    else:
        dfs(grid, x+1, y, sets, curr + grid[x][y])
        dfs(grid, x, y+1, sets, curr + grid[x][y])

def transpose(grid):
    for i in range(n):
        for j in range(n):
            if i + j >= n - 1: continue
            grid[i][j], grid[n-1-j][n-1-i] = grid[n-1-j][n-1-i], grid[i][j]

with open('palpath.in') as f:
    n = int(f.readline().strip())
    grid = [list(line.strip()) for line in f.readlines()]

rows1 = defaultdict(set)
rows2 = defaultdict(set)

dfs(grid, 0, 0, rows1, "")
transpose(grid)
dfs(grid, 0, 0, rows2, "")

ans = set()
for a in range(n):
    for s in rows1[a]:
        if s in rows2[a]:
            ans.add(s)

with open('palpath.out', 'w') as f:
    f.write(str(len(ans)) + '\n')