소문난 칠공주

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

요약
5x5 격자에서 S와 Y로 표시된 학생 중 7명이 상하좌우로 연결되고 그중 S가 4명 이상인 선택 방법의 수를 구합니다.
난이도

보통10점 중 5점

유형
백트래킹, DFS, 완전 탐색
정답자
아직 제출이 없습니다

문제

25명의 학생이 5*5 정사각형 격자 모양으로 앉아 있다. 각 학생은 S 그룹 또는 Y 그룹에 속한다.

이 가운데 7명의 학생을 골라 하나의 모임을 만들려고 한다. 모임은 다음 조건을 모두 만족해야 한다.

  1. 정확히 7명의 학생으로 이루어져야 한다.
  2. 고른 7개의 자리는 가로 또는 세로로 이어져 하나의 연결된 영역을 이루어야 한다.
  3. Y 그룹 학생이 포함되어도 된다.
  4. 단, S 그룹 학생이 적어도 4명 이상 포함되어야 한다.

자리 배치가 주어졌을 때, 조건을 만족하는 7명 모임을 만들 수 있는 경우의 수를 구하시오.

입력

첫째 줄부터 다섯 줄에 걸쳐 5*5 자리 배치가 주어진다. 각 문자는 S 또는 Y이며, 공백 없이 주어진다.

출력

조건을 만족하는 7명 모임의 경우의 수를 출력한다.

힌트

다음 그림은 가능한 선택 형태 두 가지를 보여준다.

.....    .....
SYSYS    SYSYS
....Y    .Y...
....S    .S...
.....    .....

예제1

  1. 예제 1

    입력
    YYYYY
    SYSYS
    YYYYY
    YSYYS
    YYYYY
    
    예상 출력
    2