When WAVwind is writing AI for Turing Cup, he comes across a problem: a tank is a square of four units in the map. He knows both positions of his and the enemies’ tank, also, he know the information of the whole map. WAVwind want to approach the enemies’ tanks as soon as possible, but because of the actions of enemies being unsure, he suppose their tanks are static. Please find the minimum steps of the way from present location to the enemy’s location and the direction which should be selected if you choose the minimum way.(“UP” represents moving up, “DOWN” represents moving down, “LEFT” represents moving left, “RIGHT” represents moving right.If the direction is nonunique ,print the one which is the max("UP">"DOWN">"LEFT">"RIGHT" ) ). Attention please, the tank can only moves up, down, left, right only one unit.

The fist line is the case number.
For each case, the first line contains two integers n, m, where n represents row and m represent column (10<=n,m<=20). The followed line is a n*m matrix, 1 represents blank area that the tank can move on it, 0 represents river or brick that the tank can not get across. The final 4 integers x1,y1,x2,y2 mean the coordinate of WAVwind’s tank (x1,y1) and the enemy’s tank (x2,y2).(The coordinate is the top left position of the tank, we ensure that the input are all validate, which means no two tanks has the same coordinate ).

提交代码