Find the Fox

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

문제

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

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

  1. 처음에 알파벳 F를 선택한다.
  2. 1에서 선택한 F와 상하좌우/대각선으로 인접한 알파벳 O를 선택한다.
  3. 2에서 선택한 O와 상하좌우/대각선으로 인접한 알파벳 X를 선택한다.
  4. 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를 찾아보자.