不建边表是一定比建边表要快的。
对角线跑最短路。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 550 #define inf 2000000000 using namespace std; int n,m,map[maxn][maxn][5],dis[maxn][maxn]; int dx[]={0,-1,-1,1,1},dy[]={0,-1,1,1,-1}; queue <int> q; bool vis[maxn][maxn]; char s[maxn]; bool judge(int x,int y) { if ((x>=1) && (x<=n+1) && (y>=1) && (y<=m+1)) return true; return false; } void spfa() { for (int i=1;i<=n+1;i++) for (int j=1;j<=m+1;j++) dis[i][j]=inf; dis[1][1]=0;q.push(1);q.push(1);vis[1][1]=true; while (!q.empty()) { int hx,hy; hx=q.front();q.pop();hy=q.front();q.pop(); for (int i=1;i<=4;i++) { int tx=hx+dx[i],ty=hy+dy[i]; if ((judge(tx,ty)) && (dis[tx][ty]>dis[hx][hy]+map[hx][hy][i])) { dis[tx][ty]=dis[hx][hy]+map[hx][hy][i]; if (!vis[tx][ty]) {q.push(tx);q.push(ty);vis[tx][ty]=true;} } } vis[hx][hy]=false; } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=m;j++) { if (s[j-1]=='/') {map[i][j][3]=map[i+1][j+1][1]=1;map[i][j+1][4]=map[i+1][j][2]=0;} else {map[i][j+1][4]=map[i+1][j][2]=1;map[i][j][3]=map[i+1][j+1][1]=0;} } } spfa(); if (dis[n+1][m+1]!=inf) printf("%d ",dis[n+1][m+1]); else printf("NO SOLUTION "); return 0; }