17622번 - 타일 교체 서브태스크

아래 <그림 1>에서 보인 것처럼 N×N 격자에 타일이 놓여 있고, 각 타일엔 차량 이동을 유도하는 차선이 그려져 있다. 상단 좌측에서 격자로 진입하는 차량은 차량 유도 차선을 따라 이동한다. 다양한 유도경로를 만들기 위해 각 타일은 교체가 가능하도록 설계되어 있다. 각 타일에 그려진 유도선은 크게 두 종류인데, 하나는 ‘1’ 자형이고 또 하나는 ‘L’자 형이다.

<그림 1>에서 보인 유도차선을 따라서는 차량이 도착지점에 갈 수 없다. 그러나 셋째 줄의 두 번째 타일(화살표로 표시된 곳)을 교체하면 <그림 2>에서 보인 것처럼 도착지점으로 갈 수 있는 경로가 만들어진다. 그리고 그 경로를 따라 갈 때 통과하는 타일의 개수는 19개이고, 이를 경로의 길이라고 한다. 즉, <그림 2>에서는 길이가 19인 차량 이동경로가 존재한다.

<그림 1>	<그림 2>

N×N 격자에 놓여진 타일에 관한 정보가 주어질 때, 정확히 k개의 타일을 교체하여 진입로에서부터 시작하여 도착지점까지 차량이 이동할 수 있는 경로가 만들어지는지를 결정하는 프로그램을 작성하고자 한다.

* 주의: 한 위치의 타일을 교체한다는 것은 현재 그 위치에 있는 타일과 다른 타일로 바꾸는 것을 말한다. 동일한 형태라도 놓인 방향이 다르면 다른 타일이다. 예를 들어, ‘1’자형이라도 가로 방향과 세로 방향은 다른 것이다.

차량진입로는 그림에서 보였듯이 항상 첫째줄 첫째 타일의 좌측지점이며 도착지점은 마지막 줄 마지막 타일의 우측 지점이다.

첫 번째 줄에 격자의 크기를 나타내는 정수 N(2 ≤ N ≤ 50)과, 교체할 수 있는 타일의 개수를 나타내는 k(0 ≤ k ≤ 1)가 주어진다. 이어지는 N줄 각각엔 N개의 정수가 주어지는데 각 정수는 <그림 3>에서 보인 것처럼 0과 5사이의 값을 가지며, 해당 타일에 그려진 유도선의 종류를 나타낸다.

정확히 k개의 타일을 교체하여 출발지에서 도착지까지의 경로가 존재하는지를 밝히고, 경로가 존재할 경우 경로 길이를 출력하고, 존재하지 않는다면 –1을 출력하라. 만약 입구에서 도착지점까지의 경로가 하나 이상 존재하면 최단경로의 길이를 출력하여야 한다.