68pts悬关求调

#include <bits/stdc++.h>
using namespace std;

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar(); 
	}
	return x*f;
}

int n,m;
int vis[5110][5110];
int a[5110][5110];
int ex,ey;

struct node{
	int x,y;	
	int val;
	bool operator <(const node a)const{
		return a.val<val; 
	}
};
priority_queue<node>q;

bool check(int x,int y){
	//cout<<"check"<<x<<" "<<y<<endl;
	if(x<1||x>n+1||y<1||y>m+1) return false;
	return true;
}

int main(){
	n=read();m=read();
	if((m+n)%2){
	    cout<<"NO SOLUTION";
	    return 0;
	}
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<m;j++){
			if(s[j]=='/') a[i][j+1]=1;
			else a[i][j+1]=0;
		}
	}
	vis[1][1]=1;vis[2][2]=1;
	if(a[1][1]==1) q.push({2,2,1});
	else q.push({2,2,0});
	ex=n,ey=m;
	while(!q.empty()){
		int xx,yy,vv;
		node f=q.top();
		q.pop();
		vv=f.val;//cout<<"start"<<f.x<<" "<<f.y<<endl;
		if(f.x==ex&&f.y==ey){
			if(a[ex][ey]==1){
				cout<<vv+1;
				return 0;
			}
			else{
				cout<<vv;					
				return 0;
			}
		}
		xx=f.x-1;yy=f.y-1;
		if(check(xx,yy)){
			if(!vis[xx][yy]){
				if(a[xx][yy]==1){
					//cout<<xx<<" "<<yy<<" "<<1<<endl; 
					q.push({xx,yy,vv+1});
					vis[xx][yy]=1;
				}
				else{//cout<<xx<<" "<<yy<<" "<<1<<endl; 
					q.push({xx,yy,vv});
					vis[xx][yy]=1;	
				}
			}
		}
		xx=f.x+1;yy=f.y+1;
		if(check(xx,yy)){
			if(!vis[xx][yy]){
				if(a[xx-1][yy-1]==1){
					//cout<<xx<<" "<<yy<<" "<<2<<endl; 
					if(xx==3&&yy==5) cout<<123124124<<endl;
					q.push({xx,yy,vv+1});
					vis[xx][yy]=1;
				}
				else{//cout<<xx<<" "<<yy<<" "<<2<<endl; 
					q.push({xx,yy,vv});
					vis[xx][yy]=1;	
				}
			}
		}
		xx=f.x-1;yy=f.y+1;
		if(check(xx,yy)){
			if(!vis[xx][yy]){
				if(a[xx][yy-1]==0){//cout<<xx<<" "<<yy<<" "<<3<<endl; 
					q.push({xx,yy,vv+1});
					vis[xx][yy]=1;
				}
				else{//cout<<xx<<" "<<yy<<" "<<3<<endl; 
					q.push({xx,yy,vv});
					vis[xx][yy]=1;	
				}
			}
		}
		xx=f.x+1;yy=f.y-1;	
		if(check(xx,yy)){
			if(!vis[xx][yy]){
				if(a[xx-1][yy]==0){//cout<<xx<<" "<<yy<<" "<<4<<endl; 
					q.push({xx,yy,vv+1});
					vis[xx][yy]=1;
				}
				else{//cout<<xx<<" "<<yy<<" "<<4<<endl;
					q.push({xx,yy,vv});
					vis[xx][yy]=1;	
				}
			}
		}
	}
	cout<<"NO SOLUTION";
	return 0;
}