널빤지로 늪 건너기
면접 대비시간 제한1초메모리 제한128 MB
10x10 그루터기 격자와 여러 널빤지 길이 집합이 주어질 때, 각 널빤지를 최대 한 번만 사용해 왼쪽 위 그루터기에서 오른쪽 아래 그루터기까지 최소 몇 개의 널빤지로 건널 수 있는지 구한다.
문제
나무 그루터기 위에 널빤지를 걸쳐 늪을 건너는 다리를 놓는 문제입니다.
당신은 악어가 우글거리는 늪을 건너 도망치고 있습니다. 늪의 그루터기들은 규칙적인 10×10 격자 위에 놓여 있고, 이웃한 격자점 사이의 간격은 1피트입니다. 격자의 왼쪽 위 모서리인 (1, 1) 위치에는 땅에 붙은 그루터기가 있고, 반대편 기슭인 오른쪽 아래 모서리 (10, 10) 위치에도 그루터기가 있습니다. 근처에는 널빤지 여러 개가 쌓여 있습니다.
각 널빤지는 길이가 정해져 있습니다. 널빤지는 같은 행 또는 같은 열에 있으면서 그 길이(피트 단위)만큼 정확히 떨어진 두 그루터기를 잇도록 놓을 수 있습니다. 널빤지는 가로 또는 세로로만 놓을 수 있고 대각선으로는 놓을 수 없으며, 각 널빤지는 최대 한 번만 사용할 수 있습니다. 널빤지는 두 끝 사이에 있는 다른 그루터기 위를 지나가도 되고, 널빤지끼리 서로 교차해도 됩니다.
그루터기 (1, 1)에서 출발해, 놓은 널빤지를 따라 그루터기에서 그루터기로 건너가며 (10, 10)에 도달해야 합니다. 가능한 한 적은 수의 널빤지로 건너십시오.
입력
처음 10줄은 늪을 10×10 문자 격자로 나타냅니다. 마침표(.)는 열린 물이고 별표(*)는 그루터기입니다. (1, 1)과 (10, 10)에는 항상 그루터기가 있습니다. 여기서 (r, c)는 위에서부터 r번째 행, 왼쪽에서부터 c번째 열을 뜻하며 모두 1부터 셉니다.
그다음 줄들은 각각 하나의 독립적인 널빤지 묶음을 나타냅니다(묶음은 여러 개일 수 있고, 모두 같은 늪을 공유합니다). 각 줄에서 첫 번째 정수는 사용할 수 있는 널빤지의 개수(최대 20)이고, 나머지 정수들은 그 널빤지들의 길이입니다.
출력
각 널빤지 묶음마다 한 줄씩 출력합니다.
그루터기 (1, 1)에서 출발해 (10, 10)에 도달할 수 있으면, 건너는 데 필요한 널빤지의 최소 개수를 출력합니다. 도달할 수 없으면 no solution possible을 출력합니다.
결과는 널빤지 묶음이 주어진 순서대로, 한 줄에 하나씩, 사이에 빈 줄 없이 출력합니다.