Find the Fox

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

요약

같은 행, 열, 대각선 위에 있고 연속한 두 글자가 서로 인접한 F, O, X 세 칸의 조합을 모두 센다.

문제

$N$ 행 $M$ 열의 글자판이 주어지고, 글자판의 각 칸에는 영어 알파벳 F, O, X 중 하나가 쓰여 있다.

당신은 이 글자판에서 영단어 FOX를 모두 찾아야 한다. FOX는 다음과 같은 규칙으로 찾아야 한다.

처음에 알파벳 F를 선택한다.
1에서 선택한 F와 상하좌우/대각선으로 인접한 알파벳 O를 선택한다.
2에서 선택한 O와 상하좌우/대각선으로 인접한 알파벳 X를 선택한다.
1, 2, 3 에서 선택한 F, O, X가 모두 같은 행, 또는 같은 열, 또는 같은 대각선에 있을 경우 FOX를 하나 찾은 것이다.

위 그림은 FOX를 바르게 찾은 예시이다.

위 그림은 FOX를 바르게 찾은 예시가 아닌 것들이다.

위 그림처럼 알파벳의 배치에 따라 한 알파벳이 여러 개의 FOX에 포함될 수도 있다. 겹쳐진 FOX들도 모두 구분해서 세어야 한다.

글자판이 주어지면 FOX가 모두 몇 개 있는지 구하여라.

첫째 줄에 글자판의 행과 열의 수 $N,M$ 이 공백으로 구분되어 주어진다. $(3 \leq N,M \leq 100)$

둘째 줄부터 $N$ 개의 줄에 걸쳐 글자판의 각 칸에 쓰인 알파벳이 각 행마다 $M$ 개 주어진다. 주어지는 알파벳은 모두 영어 알파벳 대문자 F, O, X 중 하나이다.

첫째 줄에 글자판에서 찾을 수 있는 FOX의 총 개수를 출력한다.

Find the Fox는 실존하는 책의 제목이다. 인내심이 충분하다면 이 책에서 FOX를 찾아보자.