In this problem,many people use the BFS(breadth first search).However,you can't search it from the two numbers which are in the last line,you should search it from the plate you need.Because of this,I was wrong before at test#6.
If your can't understand it,you can test the sample input,the right answer is- 2 1 2 but not 2 4 2
And pay attention at the number of routes-1 to 2000.
I ACed it with BFS first try! It took me 15 minutes to solve :\ What are you talking about?
～～～MY SOLUTION STAT～～～ Points nullified : 1) BFS doesn't work! 2) You can't search from the starting point. 3) Right answer isn't 2 4 2 Additional points : INCONSISTENCY NULLIFICATION : 0 corresponds to YOUR plate! Hope I made your "advice" invalid.
The key point is to build the graph (I did in K^2) and traverse it with BFS, so that you could find the SHORTEST path (K). That gives me O(K^2) in total.