两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

譯自 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.

有多組測試數(shù)據(jù)。

第一行為測試數(shù)據(jù)組數(shù)，以下每組測試數(shù)據(jù)描述為：

第一行有兩個整數(shù) N 和 M。

在接下來的 N 行中，每行有 M 個字符。每個字符均為 "\" 或 "/"，表示正方形元件上導線的連接方向。

The first line of input contains two integer numbers N and M, the dimensions of the plate. In each of the following N lines there are M symbols – either  \ or / – which indicate the direction of the wire connecting the opposite vertices of the corresponding tile.

每組測試數(shù)據(jù)輸出描述：

輸出共一行，若有解則輸出一個整數(shù)，表示至少要旋轉多少個正方形元件才能讓電源與燈泡連通；若無解則輸出 NO SOLUTION。

There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain only one integer number: the minimal number of tiles that have to be turned to switch on the lamp. If it is not possible, output the string: NO SOLUTION

1
3 5
\\/\\
\\///
/\\\\

1

對于 40% 的數(shù)據(jù)，1≤N≤4,1≤M≤5。

對于所有數(shù)據(jù)，1≤N,M≤500。