Yokohama Phenomena
Source: aizu

Yokohama Phenomena

Do you know about Yokohama Phenomena? The phenomenon takes place when three programmers, sitting around a table, hold a single pen together above a board. A grid of squares is drawn on the board, with each square marked with a single letter. Although none of the participants purposely moves the pen, its nib, as if it has a will, goes down to one of the squares marked with Y, and then starts moving on the board. The squares passed are marked with O, K, O, H, A, and M in this order, and then the nib stops on the square marked with A.

Let us call the series of squares along such a trajectory of the nib a YOKOHAMA trace. A YOKOHAMA trace is defined as follows.

It is a series of eight squares in the given grid of squares.
Every square in the series, except for the first one, shares an edge with (is edge-adjacent to) its directly preceding square in the series.
The letters marked in the eight squares of the series are Y, O, K, O, H, A, M, and A, in this order.

Note that the same square may appear more than once in the series.

Figure A.1 (a) is an illustration of the board corresponding to Sample Input 1. Figures A.1 (b) and (c) show trajectories on two of the YOKOHAMA traces. Both traces start at the leftmost square in the upper row. The same square marked with O appears twice in the trace illustrated in Figure A.1 (c).



Figure A.1. A board and trajectories on two of the YOKOHAMA traces



You are given a grid of squares, each marked with one of six letters, A, H, K, M, O, or Y. Your task is to count how many distinct YOKOHAMA traces are possible on it.

Input

The input consists of a single test case of the following format.

$n$ $m$
$x_{1,1}$ ... $x_{1,m}$
.
.
.
$x_{n,1}$ ... $x_{n,m}$


The first two integers $n$ and $m$ ($1 \leq n \leq 10, 1 \leq m \leq 10$) describe the size of the grid. The grid has squares arranged in an $n \times m$ matrix. The following n lines describe the letters marked in the squares. The square at the $i$-th row and the $j$-th column in the grid ($1 \leq i \leq n, 1 \leq j \leq m$) has letter $x_{i,j}$ marked in it. Each $x_{i,j}$ is one of the six letters, A, H, K, M, O, or Y.

Output

Output a line containing the number of distinct YOKOHAMA traces.

Sample Input 1
2 4
YOHA
OKAM

Sample Output 1
8

Sample Input 2
3 4
YOKH
OKHA
KHAM

Sample Output 2
0

Sample Input 3
3 6
MAYOHA
AHOKAM
MAYOHA

Sample Output 3
80


C++ solution:
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, m;
vector<string> grid;
string target = "YOKOHAMA";
int target_len = 8;
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int dfs(int x, int y, int index) {
    if (index == target_len - 1) return 1;

    int count = 0;
    for (int i = 0; i < 4; ++i) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        if (isValid(nx, ny) && grid[nx][ny] == target[index + 1]) {
            count += dfs(nx, ny, index + 1);
        }
    }
    return count;
}

int countYokohamaTraces() {
    int count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'Y') {
                count += dfs(i, j, 0);
            }
        }
    }
    return count;
}

int main() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    int result = countYokohamaTraces();
    cout << result << endl;

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	var n, m int
	fmt.Sscanf(scanner.Text(), "%d %d", &n, &m)

	grid := make([]string, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		grid[i] = scanner.Text()
	}

	sequence := []byte{'Y', 'O', 'K', 'O', 'H', 'A', 'M', 'A'}

	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if k == 7 {
			return 1
		}
		res := 0
		directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
		for _, dir := range directions {
			ni, nj := i+dir[0], j+dir[1]
			if ni >= 0 && ni < n && nj >= 0 && nj < m {
				if grid[ni][nj] == sequence[k+1] {
					res += dfs(ni, nj, k+1)
				}
			}
		}
		return res
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == sequence[0] {
				ans += dfs(i, j, 0)
			}
		}
	}
	fmt.Println(ans)
}

Java solution:
import java.util.*;

public class Main {
    static int n, m;
    static char[][] grid;
    static final String sequence = "YOKOHAMA";
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine(); // consume the rest of the line
        grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j < m; j++) {
                grid[i][j] = line.charAt(j);
            }
        }

        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'Y') {
                    total += dfs(i, j, 0);
                }
            }
        }
        System.out.println(total);
    }

    private static int dfs(int i, int j, int k) {
        if (k == 7) {
            return 1;
        }
        int res = 0;
        for (int dir = 0; dir < 4; dir++) {
            int ni = i + dx[dir];
            int nj = j + dy[dir];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                if (grid[ni][nj] == sequence.charAt(k + 1)) {
                    res += dfs(ni, nj, k + 1);
                }
            }
        }
        return res;
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n, m;
let grid = [];
let linesRead = 0;

rl.on('line', (line) => {
    if (linesRead === 0) {
        [n, m] = line.trim().split(' ').map(Number);
        linesRead++;
    } else {
        grid.push(line.trim());
        if (grid.length === n) {
            rl.close();
        }
    }
}).on('close', () => {
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const sequence = ['Y', 'O', 'K', 'O', 'H', 'A', 'M', 'A'];
    
    function dfs(i, j, step) {
        if (step === 7) {
            return 1;
        }
        let count = 0;
        for (const [di, dj] of directions) {
            const ni = i + di;
            const nj = j + dj;
            if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                if (grid[ni][nj] === sequence[step + 1]) {
                    count += dfs(ni, nj, step + 1);
                }
            }
        }
        return count;
    }
    
    let total = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] === 'Y') {
                total += dfs(i, j, 0);
            }
        }
    }
    
    console.log(total);
    process.exit(0);
});

Python solution:
# ICPC_1444
n, m = map(int, input().split())
x = [input() for _ in range(n)]

def dfs(i, j, k=0):
    if k==7:
        return 1
    res = 0
    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if not (0<=i+di<n and 0<=j+dj<m):
            continue
        if x[i+di][j+dj]!="YOKOHAMA"[k+1]:
            continue
        res += dfs(i+di, j+dj, k+1)
    return res

ans = 0
for i in range(n):
    for j in range(m):
        if x[i][j]=="Y":
            ans += dfs(i, j)
print(ans)

Ruby solution:
h, w = gets.chomp.split.map(&:to_i)
board = ["#" * (w + 2)]
h.times{board << "#" + gets.chomp + "#"}
board << "#" * (w + 2)

temp = []
1.upto(h){|i| 1.upto(w){|j| temp << [i, j, 1] if board[i][j] == "Y"}}
yokohama = "YOKOHAMA"
result = 0
idx = 0
while idx < temp.length
    i, j, k = temp[idx]
    idx += 1
    if k == 8
        result += 1
        next
    end
    [[i+1, j], [i-1, j], [i, j+1], [i, j-1]].each{|y, x|
        temp << [y, x, k + 1] if board[y][x] == yokohama[k]
    }
end
puts result