[BaekJoon] 1987 알파벳

by

문제

수직 R 셀과 수평 C 셀이 있는 테이블 모양의 보드가 있습니다. 보드의 각 사각형에 대문자를 쓰고 왼쪽 상단 사각형(행 1 열 1)에 조각을 놓습니다.

도형은 인접한 4개의 사각형 중 어느 곳으로든 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있으며, 새로 이동한 사각형의 문자는 이전에 지나간 모든 사각형의 문자와 달라야 합니다. 즉, 동일한 문자가 있는 셀을 두 번 전달할 수 없습니다.

왼쪽 상단 모서리에서 시작하여 문자가 지나갈 수 있는 최대 정사각형 수를 찾는 프로그램을 작성하십시오. 말이 통과하는 사각형은 왼쪽 상단 모서리에 있는 사각형을 둘러쌉니다.

I/O 예시

기입: 첫 번째 줄에서 R과 C 사이에 공백을 두고 지정합니다. (1 ≤ R,C ≤ 20) 두 번째 줄부터 R 줄까지는 공백 없이 C 대문자로 칠판에 적는다.

누르다: 첫 번째 줄은 말이 통과할 수 있는 최대 공간 수를 나타냅니다.

입력 예시 1)

2 4
CAAB
ADCB

출력 예 1)

3

입력 예시 2)

3 6
HFDFFB
AJHGDH
DGAGEH

출력 예 2)

6

입력 예시 3)

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

출력 예 3)

10

암호

import sys
input = sys.stdin.readline

R, C = map(int, input().rstrip().split())
grid = (list(input().rstrip()) for _ in range(R))
d = ((0, 1), (0, -1), (1, 0), (-1, 0))
visit = (False for _ in range(26))
visit(ord(grid(0)(0)) - 65) = True
ans = 0

def dfs(x, y, depth):
    
    global ans
    ans = max(ans, depth)

    for dx, dy in d:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < R and 0 <= ny < C and not visit(ord(grid(nx)(ny)) - 65):
            visit(ord(grid(nx)(ny)) - 65) = True
            dfs(nx, ny, depth + 1)
            visit(ord(grid(nx)(ny)) - 65) = False

dfs(0, 0, 1)
print(ans)

실행 화면


달성한 결과