레이팅 미적용설명
농부 존의 농장은 N x N 격자 모양의 밭(2 <= N <= 18)으로 이루어져 있으며, 각 밭에는 A..Z 중 한 글자가 적혀 있다.
매일 베시는 왼쪽 위 밭에서 오른쪽 아래 밭까지 걸어가며, 한 걸음마다 오른쪽으로 한 칸 또는 아래로 한 칸 이동한다. 베시는 지나간 밭들의 글자로 만들어지는 문자열을 기록하는데, 이 문자열이 팰린드롬이면 방향 감각을 잃는다.
베시가 만들 수 있는 서로 다른 팰린드롬의 개수를 구해 베시를 도와주자. 같은 팰린드롬을 만드는 서로 다른 경로는 한 번만 센다.
제약
입력 형식
첫째 줄에 N이 주어진다. 나머지 N개의 줄에는 격자의 N개 행이 주어지며, 각 행은 A..Z 범위의 문자 N개로 이루어져 있다.
출력 형식
베시가 만들 수 있는 서로 다른 팰린드롬의 개수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
palpath.in · 출력을 쓸 파일 palpath.out예제 1
입력
4
ABCD
BXZX
CDXB
WCBA출력
4설명
Output details: The four distinct palindromes are ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > US Open > Bronze
태그