타일 교체

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

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

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

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

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

각 타일의 종류는 0부터 5까지의 정수로 나타내며, 종류별 유도선의 모양은 \<그림 3>과 같다. 각 종류가 연결하는 두 변은 다음과 같다.

• 0: 오른쪽 변과 아래쪽 변을 연결 (우-하 곡선)
• 1: 왼쪽 변과 아래쪽 변을 연결 (좌-하 곡선)
• 2: 오른쪽 변과 위쪽 변을 연결 (우-상 곡선)
• 3: 왼쪽 변과 위쪽 변을 연결 (좌-상 곡선)
• 4: 위쪽 변과 아래쪽 변을 연결 (세로 직선)
• 5: 왼쪽 변과 오른쪽 변을 연결 (가로 직선)

차량은 한 타일에 어느 한 변으로 들어오면, 그 타일이 연결하는 다른 한 변으로 빠져나가 이웃한 타일로 이동한다. 격자 밖으로 빠져나가면 더 이상 진행할 수 없다.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 격자의 크기를 나타내는 정수 \(N\ (2 \le N \le 50)\) 과, 교체할 수 있는 타일의 개수를 나타내는 \(k\ (0 \le k \le 1)\) 가 주어진다.

이어지는 \(N\) 줄 각각엔 \(N\) 개의 정수가 주어지는데, 각 정수는 \<그림 3>에서 보인 것처럼 0과 5 사이의 값을 가지며, 해당 타일에 그려진 유도선의 종류를 나타낸다.

표준 출력으로, 정확히 \(k\)개의 타일을 교체하여 출발지에서 도착지까지의 경로가 존재하는지를 밝히고, 경로가 존재할 경우 경로 길이를 출력하고, 존재하지 않는다면 \(-1\)을 출력하라.

만약 입구에서 도착지점까지의 경로가 하나 이상 존재하면 최단경로의 길이를 출력하여야 한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 고등부 1번