Yokohama Phenomena

시간 제한2초메모리 제한1024 MB

요약

격자에서 변으로 맞닿은 여덟 칸을 차례로 지나며 Y, O, K, O, H, A, M, A를 만드는 경로의 개수를 센다.

난이도: 보통10점 중 4점
유형: DFS, 백트래킹, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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.

입력

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

$n$ $m$

$x\_{1,1}$ $\cdots$ $x\_{1,m}$

$\vdots$

$x\_{n,1}$ $\cdots$ $x\_{n,m}$

The first two integers $n$ and $m$ ( $1 ≤ n ≤ 10$ , $1 ≤ m ≤ 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 ≤ i ≤ n$ , $1 ≤ j ≤ 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 a line containing the number of distinct YOKOHAMA traces.

예제3

예제 1
입력
```
2 4
YOHA
OKAM
```
예상 출력
```
8
```
예제 2
입력
```
3 4
YOKH
OKHA
KHAM
```
예상 출력
```
0
```
예제 3
입력
```
3 6
MAYOHA
AHOKAM
MAYOHA
```
예상 출력
```
80
```