Yokohama Phenomena

Interview

Time limit2sMemory limit1024 MB

Summary

Count the paths of eight cells, each adjacent to the previous one, whose letters spell Y, O, K, O, H, A, M, A in order on the grid.

Level: Easy3 of 10
Topics: Brute force, Backtracking, Matrix
Solved: No attempts yet

Problem

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, and each square is marked with a single letter. None of the participants purposely moves the pen, yet its nib goes down onto one of the squares marked with Y and then starts moving across the board. The squares it passes are marked with O, K, O, H, A, and M in this order, and the nib stops on a square marked with A.

We call the series of squares along such a path of the nib a YOKOHAMA trace. A YOKOHAMA trace has the following properties.

It is a series of eight squares in the given grid.
Every square in the series, except the first one, shares an edge with the square directly before it in the series.
The letters in the eight squares are Y, O, K, O, H, A, M, and A, in this order.

The same square may appear more than once in the series.

Figure A.1 (a) shows a board. Figures A.1 (b) and (c) show trajectories on two of the YOKOHAMA traces on that board. Both traces start at the leftmost square in the top row. The trace in Figure A.1 (c) visits the same square marked with O twice.

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

You are given a grid where each square is marked with one of six letters: A, H, K, M, O, or Y. Count how many distinct YOKOHAMA traces the grid contains.

Input

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

$n$ $m$

$x_{1,1}$ $\cdots$ $x_{1,m}$

$\vdots$

$x_{n,1}$ $\cdots$ $x_{n,m}$

The first line has two integers $n$ and $m$ ( $1 \le n \le 10$ , $1 \le m \le 10$ ), the number of rows and columns of the grid. The following $n$ lines give the letters of the squares. The square in row $i$ and column $j$ ( $1 \le i \le n$ , $1 \le j \le m$ ) is marked with $x_{i,j}$ . Each $x_{i,j}$ is one of A, H, K, M, O, or Y.

Output

Output a line containing the number of distinct YOKOHAMA traces.

Examples3

Example 1
Input
```
2 4
YOHA
OKAM
```
Expected output
```
8
```
Example 2
Input
```
3 4
YOKH
OKHA
KHAM
```
Expected output
```
0
```
Example 3
Input
```
3 6
MAYOHA
AHOKAM
MAYOHA
```
Expected output
```
80
```