소문난 칠공주
시간 제한2초메모리 제한256 MB
5x5 격자에서 S와 Y로 표시된 학생 중 7명이 상하좌우로 연결되고 그중 S가 4명 이상인 선택 방법의 수를 구합니다.
문제
25명의 학생이 5*5 정사각형 격자 모양으로 앉아 있다. 각 학생은 S 그룹 또는 Y 그룹에 속한다.
이 가운데 7명의 학생을 골라 하나의 모임을 만들려고 한다. 모임은 다음 조건을 모두 만족해야 한다.
- 정확히 7명의 학생으로 이루어져야 한다.
- 고른 7개의 자리는 가로 또는 세로로 이어져 하나의 연결된 영역을 이루어야 한다.
Y그룹 학생이 포함되어도 된다.- 단,
S그룹 학생이 적어도 4명 이상 포함되어야 한다.
자리 배치가 주어졌을 때, 조건을 만족하는 7명 모임을 만들 수 있는 경우의 수를 구하시오.
입력
첫째 줄부터 다섯 줄에 걸쳐 5*5 자리 배치가 주어진다. 각 문자는 S 또는 Y이며, 공백 없이 주어진다.
출력
조건을 만족하는 7명 모임의 경우의 수를 출력한다.
힌트
다음 그림은 가능한 선택 형태 두 가지를 보여준다.
..... .....
SYSYS SYSYS
....Y .Y...
....S .S...
..... .....