自己感觉没什么问题,T三个点,加了一堆卡常T两个了
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int head,dis;
}node[251005];
struct Edge
{
int next,to,len;
}edge[1000005];
int n,m,cnt,tot;
char c[503][503];
int ord[503][503];
inline void addEdge(int u,int v,int w)
{
edge[++cnt]={node[u].head,v,w};
node[u].head=cnt;
}
inline void Dijkstra()
{
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>>q;
for(register int i=1;i<=tot;i++)
{
node[i].dis=0x3f3f3f3f;
}
node[1].dis=0;
q.push({0,1});
while(q.size())
{
pii tmp=q.top();
q.pop();
int d=tmp.first,u=tmp.second;
if(d!=node[u].dis)continue;
for(int e=node[u].head;e;e=edge[e].next)
{
int v=edge[e].to;
if(node[v].dis>d+edge[e].len)
{
node[v].dis=d+edge[e].len;
q.push({node[v].dis,v});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++)
{
scanf("%s",c[i]+1);
for(register int j=1;j<=m;j++)
ord[i][j]=++tot;
ord[i][m+1]=++tot;
}
for(register int i=1;i<=m+1;i++)
{
ord[n+1][i]=++tot;
}
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=m;j++)
{
if(c[i][j]=='/')
{
addEdge(ord[i][j],ord[i+1][j+1],1);
addEdge(ord[i+1][j+1],ord[i][j],1);
addEdge(ord[i][j+1],ord[i+1][j],0);
addEdge(ord[i+1][j],ord[i][j+1],0);
}
if(c[i][j]=='\\')
{
addEdge(ord[i][j],ord[i+1][j+1],0);
addEdge(ord[i][j+1],ord[i+1][j],1);
addEdge(ord[i+1][j+1],ord[i][j],0);
addEdge(ord[i+1][j],ord[i][j+1],1);
}
}
}
Dijkstra();
if(node[tot].dis!=0x3f3f3f3f)cout<<node[tot].dis<<endl;
else puts("NO SOLUTION");
return 0;
}