Editing 2015 Open Bronze Problem 4 Palindromic Paths (Bronze) (section)

== Code ==

=== C++ ===
<pre>
#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;
}

</pre>

=== Java ===
<pre>
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;
            }
        }
    }
}

</pre>

=== Python ===
<pre>
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')

</pre>

[[Category:Yearly_2014_2015]]
[[Category:Bronze]]
[[Category:2D Array]]
[[Category:Brute Force]]
[[Category:Simulation]]