P4667 [BalticOI 2011] Switch the Lamp On 电路维修 (Day1)

Casper is designing an electronic circuit on a $N \times M$ rectangular grid plate. There are $N \times M$ square tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are connected by a wire. A power source is connected to the top left corner of the plate. A lamp is connected to the bottom right corner of the plate. The lamp is on only if there is a path of wires connecting power source to lamp. In order to switch the lamp on, any number of tiles can be turned by 90° (in both directions).  In the picture above the lamp is off. If any one of the tiles in the second column from the right is turned by 90° , power source and lamp get connected, and the lamp is on. Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.

N/A

N/A

对于 $40\%$ 的数据，$1 \le N \le 4$，$1 \le M \le 5$。 对于所有数据，$1 \le N,M \le 500$。