思路

在格点而非格子上建两种对角线边，转动成本0/1，奇偶不可达NO SOLUTION，注意多组输入。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){int n,m;cin>>n>>m;vector<string>g(n);for(auto &s:g)cin>>s;if((n+m)%2){cout<<"NO SOLUTION\n";continue;}int w=m+1;vector<int>d((n+1)*w,INT_MAX);deque<pair<int,int>>q;d[0]=0;q.push_back({0,0});while(!q.empty()){auto p=q.front();q.pop_front();int v=p.first;if(d[v]!=p.second)continue;int x=v/w,y=v%w;for(int dx:{-1,1})for(int dy:{-1,1}){int a=x+dx,b=y+dy;if(a<0||a>n||b<0||b>m)continue;int z=a*w+b,c=g[min(x,a)][min(y,b)]!=(dx==dy?char(92):'/');if(d[z]>d[v]+c){d[z]=d[v]+c;if(c)q.push_back({z,d[z]});else q.push_front({z,d[z]});}}}cout<<d.back()<<'\n';}}