ZOJ Problem Set - 2097
A mini robot is put on a cell of a chessboard. The size of the chessboard is 8 * 8. The robot has four states denoted by integer from 1 to 4.
There is an integer in each cell of the chessboard, the integers are positive and not greater than 1000. The robot can walk up, down, left or right to one of the neighboring cells. The cost of the movement is the multiplication of the integer in the new cell and its original state, then the state of the robot is altered to (cost MOD 4 + 1). The initial state of the robot is 1.
Your task is to find the path between two given cells with the minimum total cost. Total cost is the sum of the costs for each walk along the path.
0 0 0 0
Author: CHEN, Shunbao
Source: Zhejiang University Local Contest 2004