答案与解析
正确答案:<p style="text-align: left;">#include <bits/stdc++.h> </p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=35;</p><p style="text-align: left;">const int fx[5]={0,1,0,-1};</p><p style="text-align: left;">const int fy[5]={1,0,-1,0};</p><p style="text-align: left;">int n,m,q,head,tail,tot,ans;</p><p style="text-align: left;">int num[Max][Max],dis[Max][Max][5],move[Max][Max][5][5];</p><p style="text-align: left;">bool vis[Max][Max],v[Max][Max][5];</p><p style="text-align: left;">int p[1000000][5],d[1000000][5];</p><p> </p><p style="text-align: left;">inline void bfs(int x,int y,int k1,int k2)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int sx=x+fx[k1],sy=y+fy[k1],tx=x+fx[k2],ty=y+fy[k2];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if((!num[sx][sy])||(!num[tx][ty])) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[1][1]=sx,p[1][2]=sy;</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(vis,0,sizeof(vis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[x][y]=vis[sx][sy]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head<tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span> int xx=p[head][1],yy=p[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=0;i<=3;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>int x1=xx+fx[i],y1=yy+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>if(!vis[x1][y1] && num[x1][y1])</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> vis[x1][y1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span> p[++tail][1]=x1,p[tail][2]=y1,p[tail][0]=p[head][0]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span> if(x1==tx&&y1==ty) {move[x][y][k1][k2]=p[tail][0];return;}</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void pre()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(move,43,sizeof(move));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int j=1;j<=m;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(num[i][j])</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int k=0;k<=3;k++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int l=0;l<=3;l++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(l==k) move[i][j][k][l]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span> else bfs(i,j,k,l);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void calc(int x,int y,int sx,int sy)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=1,tot=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[1][1]=x,p[1][2]=y,p[1][0]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(vis,0,sizeof(vis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[x][y]=vis[sx][sy]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head<tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span> int xx=p[head][1],yy=p[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=0;i<=3;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>int x1=xx+fx[i],y1=yy+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>if(num[x1][y1]&&!vis[x1][y1])</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span> vis[x1][y1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span> p[++tail][0]=p[head][0]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span> p[tail][1]=x1,p[tail][2]=y1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>else if(x1==sx&&y1==sy) d[++tot][1]=x1,d[tot][2]=y1,d[tot][0]=p[head][0],d[tot][3]=(i+2)%4;</p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void SPFA()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(v,0,sizeof(v));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=tot;i++) dis[d[i][1]][d[i][2]][d[i][3]]=d[i][0],v[d[i][1]][d[i][2]][d[i][3]]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=tot;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head<tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span> int x=d[head][1],y=d[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span> v[x][y][d[head][3]]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=0;i<=3;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>int x1=x+fx[i],y1=y+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>if(dis[x1][y1][(i+2)%4] > dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1)</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> dis[x1][y1][(i+2)%4]=dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(!v[x1][y1][(i+2)%4])</p><p style="text-align: left;"><span style="white-space:pre"> </span> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>tail++;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>d[tail][1]=x1,d[tail][2]=y1,d[tail][3]=(i+2)%4;</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>v[x1][y1][(i+2)%4]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>} </p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d%d%d",&n,&m,&q);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int j=1;j<=m;j++) scanf("%d",&num[i][j]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(q--)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int x,y,sx,sy,tx,ty;</p><p style="text-align: left;"><span style="white-space:pre"> </span> scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(sx==tx&&sy==ty) {cout<<"0\n";continue;}</p><p style="text-align: left;"><span style="white-space:pre"> </span> memset(dis,43,sizeof(dis));</p><p style="text-align: left;"><span style="white-space:pre"> </span> calc(x,y,sx,sy);</p><p style="text-align: left;"><span style="white-space:pre"> </span> SPFA();</p><p style="text-align: left;"><span style="white-space:pre"> </span> ans=dis[0][0][0];</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=0;i<=3;i++) ans=min(ans,dis[tx][ty][i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(ans==dis[0][0][0]) cout<<"-1\n";</p><p style="text-align: left;"><span style="white-space:pre"> </span> else cout<<ans<<"\n";</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。