也就是存个板子2333
图论题，把状态当做点，四个状态分别上下左右，然后先把空格移到起点，空格再带着起点满地图跑[/手动滑稽]
然后，，，去吧，代码菌！！
#include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<deque> #include<list> #include<set> #include<vector> #include<iostream> #define ll long long #define re register #define inf 0x7f7f7f7f #define inl inline #define sqr(x) (x*x) #define max(a,b) (a>b?a:b) #define eps 1e-8 #define debug puts("**************************"); //#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize (2) //#pragma G++ optimize (2) using namespace std; //const ll mod; const ll MAXN=35; inl ll read() { re ll x = 0; re int f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } inl char readc() { char ch=getchar(); while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar(); return ch; } inl void write(re ll x){ if(x>=10)write(x/10); putchar(x%10+'0'); } inl void writeln(re ll x){ if(x<0) {x=-x;putchar('-');} write(x); puts(""); } inl ll gcd(re ll x,re ll y) {while(y^=x^=y^=x%=y);return x;} inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;} inl void FR() { freopen(".in","r",stdin); freopen(".out","w",stdout); } inl void FC() { fclose(stdin); fclose(stdout); } ll n,m,q,mapn[MAXN][MAXN],minx,tot,en1[5],en2[5],pay[5],ex,ey; ll l[MAXN][MAXN][MAXN][MAXN],vis[MAXN][MAXN],to[5],sx,sy,tx,ty; ll d[MAXN][MAXN][MAXN][MAXN][4],see[MAXN][MAXN],tp[MAXN][MAXN]; ll dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; struct o {ll x,y,dis;}; inl void spfa(ll x,ll y,ll k) { queue<o>Q; d[x][y][x][y][k]=0; Q.push((o){x,y,0}); while(!Q.empty()) { o t=Q.front();Q.pop(); see[t.x][t.y]=0; for(re ll i=0;i<4;i++) { re ll xx=t.x+dx[i],yy=t.y+dy[i]; if(mapn[xx][yy]&&d[x][y][xx][yy][k]>d[x][y][t.x][t.y][k]+l[t.x][t.y][xx][yy]&&l[t.x][t.y][xx][yy]) { d[x][y][xx][yy][k]=d[x][y][t.x][t.y][k]+l[t.x][t.y][xx][yy]; if(!see[xx][yy]) { see[xx][yy]=1;Q.push((o){xx,yy,0}); } } } } } inl void bfs() { queue<o>Q; Q.push((o){ex,ey,0}); vis[ex][ey]=0; while(!Q.empty()) { o t=Q.front();Q.pop(); for(re ll i=0;i<4;i++) { re ll xx=t.x+dx[i],yy=t.y+dy[i]; if(vis[xx][yy]) { if(xx==sx&&yy==sy) { tot++; to[tot]=i; en1[tot]=t.x; en2[tot]=t.y; pay[tot]=t.dis; } else { vis[xx][yy]=0; Q.push((o){xx,yy,t.dis+1}); } } } } } void dfs(ll x,ll y,ll fa1,ll fa2,ll to,ll tott) { if(tott>=minx) return ; if(x==tx&&y==ty) {minx=tott;return ;} mapn[x][y]=0; for(re ll i=0;i<4;i++) { re ll xx=x+dx[i],yy=y+dy[i]; if(d[fa1][fa2][xx][yy][to]<1e5&&!tp[xx][yy]) { tp[xx][yy]=1; dfs(xx,yy,x,y,i,tott+d[fa1][fa2][xx][yy][to]+1); tp[xx][yy]=0; } } mapn[x][y]=1; } int main() { // FR(); memset(d,1,sizeof(d)); n=read(),m=read(),q=read(); for(re ll i=1;i<=n;i++) { for(re ll j=1;j<=m;j++) { mapn[i][j]=read(); } } for(re ll i=1;i<=n;i++) { for(re ll j=1;j<=m;j++) { for(re ll k=0;k<4;k++) { re ll xx=i+dx[k],yy=j+dy[k]; if(mapn[xx][yy]){ l[xx][yy][i][j]=1; l[i][j][xx][yy]=1; } } } } for(re ll i=1;i<=n;i++) { for(re ll j=1;j<=m;j++) { for(re ll k=0;k<4;k++) { re ll xx=i+dx[k],yy=j+dy[k]; if(mapn[i][j]&&mapn[xx][yy]) { mapn[xx][yy]=0; spfa(i,j,k); mapn[xx][yy]=1; } } } } for(re ll t=1;t<=q;t++) { for(re ll i=1;i<=n;i++) { for(re ll j=1;j<=m;j++) vis[i][j]=mapn[i][j]; } ex=read(),ey=read(); sx=read(),sy=read(); tx=read(),ty=read(); tot=0; if(sx==tx&&sy==ty) {puts("0");continue ;} bfs(); if(!tot) {puts("-1");continue ;} minx=9999999; for(re ll i=1;i<=tot;i++) { dfs(sx,sy,en1[i],en2[i],to[i],pay[i]); } writeln((minx==9999999)?-1:minx); } // FC(); return 0; }