PDF《电路维修》

电路维修 (cir.

pas/c/cpp) 题目描述 Elf 是来自 Gliese 星球的少女, 由于偶然的原因 漂流到了地球上.在她无依无靠的时候,善良的运 输队员 Mark 和James 收留了她.Elf 很感谢 Mark 和James,可是一直也没能给他们帮上什么忙. 有一天 Mark 和James 的飞行车没有办法启动 了,经过检查发现原来是电路板的故障.飞行车的 电路板设计很奇葩,如下图所示: 电路板可以表示为一个 R 行C列的方格表,每个格子中都有一个标准件,连接一条对 角线上的两个接点.标准件的方向可以旋转,从而连接另一条对角线的两个接点.电源与左 上角的接点相连,而发动机与右下角的接点相连.Mark 和James 发现现在电源和发动机根 本就没有连上.出于对这种奇葩设计的尊重,他们只能通过旋转标准件来维修电路. Elf 想要帮助他们,让他们旋转标准件的次数尽量小,但是电路的规模实在是太大了, 于是她找到了你,希望你能够帮助她解决这个问题. 输入格式 输入文件包含多组测试数据.第一行包含一个整数 T 表示测试数据的数目. 对于每组测试数据,第一行包含正整数 R 和C,表示电路板的行数和列数. 之后 R 行,每行 C 个字符,字符是"/"和"\"中的一个,表示标准件的方向. 输出格式 对于每组测试数据,在单独的一行输出一个正整数,表示所需的缩小旋转次数. 如果无论怎样都不能使得电源和发动机之间连通,输出 NO SOLUTION. 样例输入

1 3

5 \\/\\ \\/// /\\\\ 样例输出

1 样例解释 样例的输入对应于题目描述中的情况. 只需要按照下面的方式旋转标准件,就可以使得电源和发动机之间连通. 数据范围与约定 对于 40% 的数据,R,C≤5. 对于 100% 的数据,R,C≤500,T≤5.