电路维修
题号:NC50261
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

有一种正方形的电路元件,在它的两组相对顶点中,有一组会用导线连接起来,另一组则不会。有个这样的元件,你想将其排列成N行M列放在电路板上。电路板的左上角连接电源,右下角连接灯泡。试求:至少要旋转多少个正方形元件才能让电源与灯泡连通,若无解则输出

输入描述:

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

输出描述:

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

输入

复制
3 5
\\/\\
\\///
/\\\\

输出

复制
1

备注:

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