qtcy

//线路维修 #include<bits/stdc++.h> using namespace std;

const int N=504; typedef pair<int,int>pII; int r,c; char g[N][N]; int dist[N][N]; int vis[N][N];

int bfs(){ memset(dist,0x3f,sizeof dist); memset(vis,0,sizeof vis); deque q; q.push_back({0,0}); dist[0][0]=0; int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1}; int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1}; char s[]="\/\/"; //用"\"表示'' while(q.size()){ auto t=q.front();q.pop_front(); int x=t.first,y=t.second; if(vis[x][y]) continue; vis[x][y]=1; for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i]; int ixx=x+ix[i],iyy=y+iy[i]; if(xx<0 || xx>r || yy<0 ||yy>c) continue; int w=(g[ixx][iyy] !=s[i]); if(dist[x][y]+w<dist[xx][yy]){ dist[xx][yy]=dist[x][y]+w; if(w==0) q.push_front({xx,yy}); else q.push_back({xx,yy}); } } } if(dist[r][c]==0x3f3f3f3f) return -1; else return dist[r][c]; }

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