아래 <그림 1>에서 보인 것처럼 N×N 격자에 타일이 놓여 있고, 각 타일엔 차량 이동을 유도하는 차선이 그려져 있다.

상단 좌측에서 격자로 진입하는 차량은 차량유도 차선을 따라 이동한다.

다양한 유도경로를 만들기 위해 각 타일은 교체가 가능하도록 설계되어 있다.

각 타일에 그려진 유도선은 크게 두 종류인데, 하나는 ‘1’자형이고 또 하나는 ‘L’자 형이다.

<그림 1>에서 보인 유도차선을 따라서는 차량이 도착지점에 갈 수 없다.

그러나 셋째 줄의 두 번째 타일(화살표로 표시된 곳)을 교체하면 <그림 2>에서 보인 것처럼 도착지점으로 갈 수 있는 경로가 만들어진다.

그리고 그 경로를 따라 갈 때 통과하는 타일의 개수는 19개이고, 이를 경로의 길이라고 한다.

즉, <그림 2>에서는 길이가 19인 차량 이동경로가 존재한다.

N×N 격자에 놓여진 타일에 관한 정보가 주어질 때, 정확히 k 개의 타일을 교체하여 진입로에서부터 시작하여

도착지점까지 차량이 이동할 수 있는 경로가 만들어지는지를 결정하는 프로그램을 작성하고자 한다.

* 주의: 한 위치의 타일을 교체한다는 것은 현재 그 위치에 있는 타일과 다른 타일로 바꾸는 것을 말한다.

동일한 형태라도 놓인 방향이 다르면 다른 타일이다. 예를들어, ‘1’자형이라도 가로 방향과 세로 방향은 다른 것이다.

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

타일교체(tile) timer 1초 memory 1024MB

타일교체(tile) 1초 1024MB