8009 : 격자 경로
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$7 \times 7$ 격자에서 좌측 상단 $(1,1)$에서 출발하여 우측 하단 $(7,1)$까지 이동하려고 합니다. 격자의 모든 칸을 정확히 한 번씩만 방문하면서 끝점에 도달하는 유효한 경로를 찾고자 합니다.
경로의 총 길이는 정확히 48이며, 이동 방향은
이동 경로의 일부 방향이 미리 주어진 문자열(길이 48, 미정 방향은
[제약 조건]
• 격자의 크기는 $7 \times 7$이며 총 48회의 이동을 수행합니다.
• 입력 문자열은 48글자이며
경로의 총 길이는 정확히 48이며, 이동 방향은
U (위), D (아래), L (왼쪽), R (오른쪽)로 표현됩니다.이동 경로의 일부 방향이 미리 주어진 문자열(길이 48, 미정 방향은
?)과 일치하는 서로 다른 경로의 개수를 구하는 프로그램을 작성하십시오.[제약 조건]
• 격자의 크기는 $7 \times 7$이며 총 48회의 이동을 수행합니다.
• 입력 문자열은 48글자이며
U, D, L, R, ?로만 구성됩니다.입력 설명
첫째 줄에 48개의 문자로 이루어진 문자열이 주어집니다.
출력 설명
조건을 만족하는 유효한 경로의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
??????R??????D??????U??????R??????D??????U??????
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
경로 수가 매우 많으므로 강력한 가지치기(Pruning)가 필수적입니다.
1. 현재 위치에서 이미 앞이 막혀있는데 좌우가 모두 뚫려 있는 경우(또는 좌우가 막혀있는데 앞뒤가 뚫린 경우) 격자가 고립된 두 영역으로 분리되므로 즉시 백트래킹을 중단합니다.
2. 끝점 $(7,1)$에 48단계 이전에 도달한 경우 탐색을 조기 종료합니다.
1. 현재 위치에서 이미 앞이 막혀있는데 좌우가 모두 뚫려 있는 경우(또는 좌우가 막혀있는데 앞뒤가 뚫린 경우) 격자가 고립된 두 영역으로 분리되므로 즉시 백트래킹을 중단합니다.
2. 끝점 $(7,1)$에 48단계 이전에 도달한 경우 탐색을 조기 종료합니다.