有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会，有 N×M 个这样的元件，你想将其排列成 N 行 M 列放在电路板上，电路板的左上角连接电源，右下角连接灯泡，Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.
译自 BalticOI 2011 Day1 T3「Switch the Lamp On」 有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。 有 N×M 个这样的元件，你想将其排列成 N 行 M 列放在电路板上。电路板的左上角连接电源，右下角连接灯泡。 试求：至少要旋转多少个正方形元件才能让电源与灯泡连通，若无解则输出 NO SOLUTION。 Casper is designing an electronic circuit on a N×M rectangular grid plate. There are N×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.
