6132 : 사다리 게임
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
사다리 게임은 N개의 세로선과 H개의 가로선 위치 정보가 주어집니다.
이미 배치되어 있는 M개의 가로선 정보가 주어질 때, i번 세로선에서 출발한 사다리 타기 결과가 반드시 i번으로 떨어지도록 조작하고 싶습니다. 이를 위해 추가로 배치해야 하는 가로선의 최소 개수를 구하시오. (3개 이하로 불가능하면 -1을 출력하며, 가로선은 연속되거나 붙어서 배치될 수 없습니다.)
이미 배치되어 있는 M개의 가로선 정보가 주어질 때, i번 세로선에서 출발한 사다리 타기 결과가 반드시 i번으로 떨어지도록 조작하고 싶습니다. 이를 위해 추가로 배치해야 하는 가로선의 최소 개수를 구하시오. (3개 이하로 불가능하면 -1을 출력하며, 가로선은 연속되거나 붙어서 배치될 수 없습니다.)
입력 설명
첫째 줄에 세로선 수 N, 가로선 수 M, 가로선을 놓을 수 있는 위치 H (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ N×H)가 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 가로선의 정보 a, b (a번째 가로 위치에서 b번과 b+1번 세로선을 연결함)가 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 가로선의 정보 a, b (a번째 가로 위치에서 b번과 b+1번 세로선을 연결함)가 주어집니다.
출력 설명
조건을 만족하도록 추가해야 하는 가로선 개수의 최솟값을 출력합니다. 3개 이하로 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2 1 3
1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
DFS 백트래킹을 통하여 가로선을 놓을 수 있는 격자 위치에 1개, 2개, 3개를 직접 두어보고, 매 배치마다 사다리 타기 결과가 원래 자기 노드로 떨어지는지 시뮬레이션 검사하십시오.