deque + BFS 64pts

#include<bits/stdc++.h>
using namespace std;
const int MaxN = 3e5 + 9;

int n, m, dis[MaxN], to;
std::vector<std::pair<int, int> > d[MaxN];
std::deque<int> q;
char mp[505][505];

void bfs(){
	memset(dis, 9, sizeof(dis));
	dis[1] = 0, q.push_back(1);
	while(q.size()){
		int x = q.front(); q.pop_front();
		for(int i = 0; i < d[x].size(); ++i){
			int y = d[x][i].first, val = d[x][i].second;
			if(dis[y] > dis[x] + val){
				dis[y] = dis[x] + val;
				if(!q.empty() and dis[y] <= dis[q.front()]) q.push_front(y);
				else q.push_back(y);
			}
		}
	}
	if(dis[to] == 151587081) printf("NO SOLUTION\n");
	else printf("%d\n", dis[to]);
}

int tag(int x, int y){
	return (x - 1) * (m + 1) + y;
}

signed main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i){
		scanf("%s", mp[i] + 1);
	}
	to = tag(n, m);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(mp[i][j] == '\\'){
				d[tag(i, j)].push_back(make_pair(tag(i + 1, j + 1), 0));
				d[tag(i + 1, j)].push_back(make_pair(tag(i, j + 1), 1));
				d[tag(i + 1, j + 1)].push_back(make_pair(tag(i, j), 0));
				d[tag(i, j + 1)].push_back(make_pair(tag(i + 1, j), 1));
			} 
			else{
				d[tag(i, j)].push_back(make_pair(tag(i + 1, j + 1), 1));
				d[tag(i + 1, j)].push_back(make_pair(tag(i, j + 1), 0));
				d[tag(i + 1, j + 1)].push_back(make_pair(tag(i, j), 1));
				d[tag(i, j + 1)].push_back(make_pair(tag(i + 1, j), 0));
			}
		}
	}
	bfs();
	return 0;
}