改了好多遍还是68
bfs+deque
#include<bits/stdc++.h>
#include<bits/extc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
namespace FAST_IO
{
template<typename T> void read(T &a)
{
a=0;
int f=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')
{
f=-1;
}
c=getchar();
}
while(isdigit(c))
{
a=a*10+c-'0';
c=getchar();
}
a=a*f;
}
template<typename T> void read(T &a,T &b ...)
{
read(a);
read(b);
}
template <typename T> void write(T a)
{
if(a<0)
{
a=-a;
putchar('-');
}
if(a>9)
{
write(a/10);
}
putchar(a%10+'0');
}
template<typename T> void write(T &a,T &b ...)
{
write(a);
putchar(' ');
wirte(b);
}
template <typename T> void writeln(T a)
{
write(a);
puts("");
}
template<typename T> void writeln(T &a,T &b ...)
{
write(a);
puts("");
wirte(b);
}
}
const int maxn=502*502;
int n,m;
vector<pair<int,int> > g[maxn];
int getpos(int x,int y)
{
return (x-1)*(m+1)+y;
}
int vis[maxn],flag;
void bfs()
{
deque<pair<int,int> > q;
q.push_back(make_pair(getpos(1,1),0));
while(q.size())
{
int from=q.front().first,now=q.front().second;
if(from==getpos(n+1,m+1))
{
flag=true;
cout<<now;
return;
}
q.pop_front();
for(int i=0;i<g[from].size();i++)
{
int to=g[from][i].first,len=g[from][i].second;
if(vis[to])
{
continue;
}
if(!len)
{
q.push_front(make_pair(to,now));
}
else
{
q.push_back(make_pair(to,now+1));
}
vis[to]=true;
}
}
}
int main()
{
//1,1~n+1,m+1
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
int from=getpos(i,j),to=getpos(i+1,j+1);
int afrom=getpos(i,j+1),ato=getpos(i+1,j);
//cout<<from<<" "<<to<<endl;
if(c=='\\')
{
g[to].push_back(make_pair(from,0));
g[from].push_back(make_pair(to,0));
g[afrom].push_back(make_pair(ato,1));
g[ato].push_back(make_pair(afrom,1));
}
if(c=='/')
{
g[ato].push_back(make_pair(afrom,0));
g[afrom].push_back(make_pair(ato,0));
g[from].push_back(make_pair(to,1));
g[to].push_back(make_pair(from,1));
}
}
}
bfs();
if(flag)
{
return 0;
}
cout<<"NO SOLUTION";
}