Double ended queue wide search is a kind of Dijkstra algorithm, which mainly solves the shortest path problem in which the weight of the edge in the graph is only 0 or 1.

Operation:

Every time you take out elements from the team head and expand other elements

1. If the edge weight of an extended element is 0, the element is inserted into the team head
2. If the edge weight of an extended element is 1, the element is inserted at the end of the team

175. Circuit maintenance

Dada is a witch from a different world. When she drifted aimlessly around, she met a kind girl Han Han and was taken in on the earth.

Han Han has a flying car in his home.

One day, the circuit board of the flying car suddenly failed, resulting in failure to start.

The overall structure of the circuit board is a grid of RR rows and CC columns (R,C ≤ 500R,C ≤ 500), as shown in the figure below.

Each grid point is the contact of wires, and each grid contains an electronic component.

The main part of the electronic component is a rotatable short cable connecting two contacts on a diagonal.

After rotation, it can connect the two contacts of another diagonal.

The contact at the upper left corner of the circuit board is connected to the DC power supply, and the contact at the lower right corner is connected to the starting device of the flying vehicle.

Dada found that the circuit board may be in an open circuit state because the direction of some components accidentally changed.

She plans to rotate the minimum number of components through calculation, so that the power supply and the starting device are connected through several short cables.

However, the scale of the circuit is too large. Dada is not good at programming. I hope you can help her solve this problem.

Note: only oblique line segments can be taken, and horizontal and vertical line segments cannot be taken.

Input format

The input file contains multiple sets of test data.

The first row contains an integer TT indicating the number of test data.

For each set of test data, the first row contains positive integers RR and CC, indicating the number of rows and columns of the circuit board.

Then RR line, CC characters in each line. The character is one of "/" and "\", indicating the direction of standard parts.

Output format

For each set of test data, a positive integer is output on a separate line, representing the minimum number of rotations required.

If the power supply and the engine cannot be connected in any way, output NO SOLUTION.

Data range

1≤R,C≤5001≤R,C≤500,
1≤T≤51≤T≤5

Input sample:

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

Output example:

1

Example explanation

The input of the sample corresponds to the situation in the title description.

Just rotate the standard part in the following way to connect the power supply and the engine.

Idea:

That is, the point that can be extended without rotation is regarded as the weight of 0

The points that need to be rotated to expand to are considered to have a weight of 1

code:

#include<iostream>
#include<deque>
#include<cstring>

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 510;
int m, n, t;
char g[N][N];
int dist[N][N];
bool st[N][N];
char c[5] = "\\/\\/";
//Coordinates of 4 locations that can be extended
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
//Coordinate difference of 4 positions that can be expanded (expanded to the grid to be stepped in 4 directions)
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};

int bfs() {
    deque<PII> q;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    q.push_back({0, 0});
    while (q.size()) {
        auto t = q.front();
        q.pop_front();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        for (int i = 0; i < 4; ++i) {
            int a = t.x + dx[i];
            int b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            int ca = t.x + ix[i], cb = t.y + iy[i];
            //(G [Ca] [CB]! = C [i]) judge the direction of the stepped grid and determine the weight
            int d = dist[t.x][t.y] + (g[ca][cb] != c[i]);
            if (d < dist[a][b]) {
                dist[a][b] = d;
                if (g[ca][cb] != c[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[n][m];
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            cin >> g[i];
        if (n + m & 1) cout << "NO SOLUTION" << endl;
        else cout << bfs() << endl;
    }
    return 0;
}