#Pybt441. 【例题1】电路维修

【例题1】电路维修

【例题1】电路维修

题目描述

有一种正方形的电路元件,在它的两组相对顶点中,有一组会用导线连接起来,另一组则不会。

有 N×M 个这样的元件,你想将其排列成 N 行 M 列放在电路板上。电路板的左上角连接电源,右下角连接灯泡。

![1448.jpg.gif](file://463a42dcec.gif)

试求:至少要旋转多少个正方形元件才能让电源与灯泡连通,若无解则输出 NO SOLUTION。

输入格式

有多组测试数据。

第一行为测试数据组数,以下每组测试数据描述为:

第一行有两个整数 N 和 M。

在接下来的 N 行中,每行有 M 个字符。每个字符均为 "" 或 "/",表示正方形元件上导线的连接方向。

输出格式

每组测试数据输出描述:

输出共一行,若有解则输出一个整数,表示至少要旋转多少个正方形元件才能让电源与灯泡连通;若无解则输出 NO SOLUTION。

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于 40% 的数据,1≤N≤4,1≤M≤5。

对于所有数据,1≤N,M≤500。