此题主要是预处理比较难

以下代码把 V(i,j,k) 当做一个**顶点** 表示 (i,j)这个点的**k**方向(k<4)有空白格

那么**(i,j) 的 k 方向**的点 (x,y) 的(k^1)方向 (k=0时k^1=1 k=2时k^1=3) 也就是相反方向(初始化移动方向时注意**0和1对应,2和3对应**)

这两个状态互相转换的步数是1,建立一条**V(i,j,k)到V(x,y,k^1)**权值为**1**的边

还有就是** (i,j) 的k方向和l方向**之间的转换**( l不等于k) **可以理解为掉头ヽ(ˋДˊ)ノ

即建立一条 **V(i,j,k) 到 V(i,j,l) **的边 权值为 **dist= (ik,jk) 到(il,jl)不经过 (i,j)的最短距离 **
-------**(ik,jk)** 表示**(i,j)的k方向**的那个点

然后**起点**有四个 ,分别是 S(起点) 的四个方向 (Sx,Sy,Ki)

初始值就为 E 点(空白点)到**(Sxk,Syk)** 不经过S的最短距离

直接最短路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 1110
#define inf 0x7f7f7f7f
#define P(x,y) (x*(m+1)+y)
//#define V(x,y,k) (rank[P(x,y)][k])
#define V(A,K) (Rank[A][K])
#define NP(A,K) (A+D[K]) 
int D[4]={-1,1};
//static const int D[]={-1,1,-m-1,m+1};//

int n,m,q;
 
int Rank[N][4];//V(i,j,k)表示(i,j)点k方向有空白格子 
int R=0;

int map[N];

struct Edge{
    int v,val;
    Edge *link;
};

Edge *graph[N*4];
Edge node[N*50];
int top=0;

inline void add(int u,int v,int val) {
    Edge *p=&node[top++];
    p->v=v;
    p->val=val;
    p->link=graph[u];
    graph[u]=p;
}

typedef pair<int,int> pii;
bool vis[N];// used for BFS
queue<pii> qq;

int BFS(const int u,const int v,const int k) {//u to v do not through k
    if( u==k || v==k ) return inf;
    if( u==v ) return 0;
    
    while(!qq.empty()) qq.pop();
    memset(vis,false,sizeof(vis));

    int l,y;
    qq.push(make_pair(u,0));
    vis[u]=true;
    while(!qq.empty()) {
        pii t=qq.front();qq.pop();
        for(l=0;l<4;l++) {
            y=NP(t.first,l);
            if( vis[y] || y==k || !map[y] ) continue;
            if( y==v ) 
                return t.second+1;
            qq.push(make_pair(y,t.second+1));
            vis[y]=true;
        }
    }
    return inf;
}

bool inq[N*4];// used for spfa
int dist[N*4];
queue<int> Q;

void spfa() {
    while(!Q.empty()) {
        int t=Q.front();Q.pop();
        inq[t]=false;
        for(Edge *p=graph[t];p;p=p->link) {
            int v=p->v;
            if(dist[v]>dist[t]+p->val) {
                dist[v]=dist[t]+p->val;
                if(!inq[v]) {
                    inq[v]=true;
                    Q.push(v);
                }
            }
        }
    }
}


int main(){
    //freopen("puzzle.in","r",stdin);
    //freopen("out.txt","w",stdout);
    
    int i,j,k,l;
    scanf("%d%d%d",&n,&m,&q);
    
    //因为是从1开始存，所以每排是(m+1) 
    //static const int D[]={-1,1,-m-1,m+1};//
    D[2]=-m-1;  D[3]=m+1;
    //                left right up down  
    
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) {
        scanf("%d",&map[P(i,j)]);
        if(map[P(i,j)]) for(k=0;k<4;k++) //give the node number
            Rank[P(i,j)][k]=R++;
    }
    
    int u,v,t;
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) 
    if( map[ u=P(i,j) ] )
    for(k=0;k<4;k++) if( map[ v=NP(u,k)] ){
        //link a way val 1 V(u,k) to V(v,k^1)
        // k^1 means 1 aginst 0 (left right) 2 aginst 3 (up down)
        add(V(u,k),V(v,k^1),1);
        
        for(l=0;l<4;l++) if( l!=k&& map[ t=NP(u,l)] ) {//turn 
            // find a way do not through U  V to T D=dist
            // if D !=inf then link a way V(U,k) to V(U,l)
            int D=BFS(v,t,u);
            if(D!=inf) 
                add(V(u,k),V(u,l),D);
        }
    }   
    
    int Ex,Ey,Sx,Sy,Tx,Ty;
    
    while(q--) {
        scanf("%d%d%d%d%d%d",&Ex,&Ey,&Sx,&Sy,&Tx,&Ty);
        
        if( (Ex==Sx&&Ey==Sy) || !map[P(Ex,Ey)] || !map[P(Sx,Sy)] || !map[P(Tx,Ty)] ) {
            printf("-1\n");
            continue;   
        }
        if( Tx==Sx&&Ty==Sy ) {
            printf("0\n");
            continue;
        }
        
        for(i=0;i<=R;i++) dist[i]=inf;
        
        u=P(Sx,Sy);
        for(k=0;k<4;k++) if( map[ v=NP(u,k)] ){
            // find a way do not through u | E to v D=dist
            // if D != inf push into SPFA_queue and put dist[v]=D
            int D=BFS(P(Ex,Ey),v,u);
            if(D==inf) continue;
            
            Q.push(V(u,k));
            dist[V(u,k)]=D;
            inq[V(u,k)]=true;
        }
        spfa();
        int ans=inf;
        u=P(Tx,Ty);
        for(k=0;k<4;k++) 
            if(ans>dist[V(u,k)])
                ans=dist[V(u,k)];
        printf("%d\n",ans==inf?-1:ans); 
    }
    
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

70分
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <map>
#include <cstring>
#define rep(i, x, y) for (int i = x; i <= y; ++i)

using namespace std;

struct status {
int ex, ey, sx, sy;
};
int n, m, q;
int mp[32][32];
int vis[810005], step[810005];
status qu[810005];
int x[4] = {0, 0, -1, 1}, y[4] = {1, -1, 0, 0};

inline int co(int a, int b, int c, int d) {
return 27000 * (a - 1) + 900 * (b - 1) + 30 * (c - 1) + d;
}
inline int bfs(int ex, int ey, int sx, int sy, int tx, int ty) {
memset(vis, 0, sizeof (vis));
memset(step, 0, sizeof (step));
int hd, tl;
qu[hd = tl = 0] = (status){ex, ey, sx, sy};
status s;
while (hd <= tl) {
s = qu[hd];
// printf("step:%d <%d %d %d %d>\n",step[hd], s.ex, s.ey, s.sx, s.sy);
if (s.sx == tx && s.sy == ty) return step[hd];
if (vis[co(s.ex, s.ey, s.sx, s.sy)]) {++hd; continue;}
vis[co(s.ex, s.ey, s.sx, s.sy)] = true;
rep(i, 0, 3) {
if (!mp[s.ex + x[i]][s.ey + y[i]]) continue;
if (s.ex + x[i] == s.sx && s.ey + y[i] == s.sy) {
qu[++tl] = s;
swap(qu[tl].ex, qu[tl].sx);
swap(qu[tl].ey, qu[tl].sy);
step[tl] = step[hd] + 1;
}
else {
qu[++tl] = s;
qu[tl].ex += x[i];
qu[tl].ey += y[i];
step[tl] = step[hd] + 1;
}
}
++hd;
}
return -1;
}
int main(int argc, const char *argv[]) {
scanf("%d %d %d", &n, &m, &q);
rep(i, 1, n) rep(j, 1, m) scanf("%d", &mp[i][j]);
int ex, ey, sx, sy, tx, ty;
rep(i, 1, q) {
scanf("%d %d %d %d %d %d", &ex, &ey, &sx, &sy, &tx, &ty);
printf("%d\n", bfs(ex, ey, sx, sy, tx, ty));
}
return 0;
}

因为没特判起点=终点WA成暴力分...

blog
有两篇题解
包明白
http://www.ofsxb.com/archives/508

60分弃疗 ， 好麻烦。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
int x1 , y1 , x2 , y2 , step;
};
int map[ 35 ][ 35 ] , n , m , q;
bool s[ 35 ][ 35 ][ 35 ][ 35 ];
void BFS(){
queue <Node> que;
int u , v , step , x1 , x2 , y1 , y2;
Node p;
memset( s , false , sizeof( s ) );
scanf( "%d%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &u , &v );
s[ x1 ][ y1 ][ x2 ][ y2 ] = true;
p.x1 = x1 , p.x2 = x2 , p.y1 = y1 , p.y2 = y2 , p.step = 0;
que.push( p );
while( !que.empty() ){
p = que.front();
que.pop();
x1 = p.x1 , y1 = p.y1 , x2 = p.x2 , y2 = p.y2 , step = p.step;
if ( x1 - 1 == x2 && y1 == y2 ){
if ( !s[ x2 ][ y2 ][ x1 ][ y1 ] ){
s[ x2 ][ y2 ][ x1 ][ y1 ] = true;
p.x1 = x2 , p.y1 = y2 , p.x2 = x1 , p.y2 = y1;
p.step = step + 1;
if ( x1 == u && y1 == v ){
printf( "%d\n" , p.step );
return;
}
que.push( p );
}
}
else{
if ( !s[ x1 - 1 ][ y1 ][ x2 ][ y2 ] && map[ x1 - 1 ][ y1 ] ){
s[ x1 - 1 ][ y1 ][ x2 ][ y2 ] = true;
p.x1 = x1 - 1 , p.y1 = y1 , p.x2 = x2 , p.y2 = y2;
p.step = step + 1;
que.push( p );
}
}
if ( x1 + 1 == x2 && y1 == y2 ){
if ( !s[ x2 ][ y2 ][ x1 ][ y1 ] ){
s[ x2 ][ y2 ][ x1 ][ y1 ] = true;
p.x1 = x2 , p.y1 = y2 , p.x2 = x1 , p.y2 = y1;
p.step = step + 1;
if ( x1 == u && y1 == v ){
printf( "%d\n" , p.step );
return;
}
que.push( p );
}
}
else{
if ( !s[ x1 + 1 ][ y1 ][ x2 ][ y2 ] && map[ x1 + 1 ][ y1 ] ){
s[ x1 + 1 ][ y1 ][ x2 ][ y2 ] = true;
p.x1 = x1 + 1 , p.y1 = y1 , p.x2 = x2 , p.y2 = y2;
p.step = step + 1;
que.push( p );
}
}
if ( x1 == x2 && y1 - 1 == y2 ){
if ( !s[ x2 ][ y2 ][ x1 ][ y1 ] ){
s[ x2 ][ y2 ][ x1 ][ y1 ] = true;
p.x1 = x2 , p.y1 = y2 , p.x2 = x1 , p.y2 = y1;
p.step = step + 1;
if ( x1 == u && y1 == v ){
printf( "%d\n" , p.step );
return;
}
que.push( p );
}
}
else{
if ( !s[ x1 ][ y1 - 1 ][ x2 ][ y2 ] && map[ x1 ][ y1 - 1 ] ){
s[ x1 ][ y1 - 1 ][ x2 ][ y2 ] = true;
p.x1 = x1 , p.y1 = y1 - 1 , p.x2 = x2 , p.y2 = y2;
p.step = step + 1;
que.push( p );
}
}
if ( x1 == x2 && y1 + 1 == y2 ){
if ( !s[ x2 ][ y2 ][ x1 ][ y1 ] ){
s[ x2 ][ y2 ][ x1 ][ y1 ] = true;
p.x1 = x2 , p.y1 = y2 , p.x2 = x1 , p.y2 = y1;
p.step = step + 1;
if ( x1 == u && y1 == v ){
printf( "%d\n" , p.step );
return;
}
que.push( p );
}
}
else{
if ( !s[ x1 ][ y1 + 1 ][ x2 ][ y2 ] && map[ x1 ][ y1 + 1 ] ){
s[ x1 ][ y1 + 1 ][ x2 ][ y2 ] = true;
p.x1 = x1 , p.y1 = y1 + 1 , p.x2 = x2 , p.y2 = y2;
p.step = step + 1;
que.push( p );
}
}
}
printf( "-1\n" );
}
int main(){
freopen( "puzzle.in" , "r" , stdin );
freopen( "puzzle.out" , "w" , stdout );
scanf( "%d%d%d" , &n , &m , &q );
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= m ; j++ )
scanf( "%d" , &map[ i ][ j ] );
for( int i = 1 ; i <= q ; i++ )
BFS();
fclose( stdin );
fclose( stdout );

}

一个数组预处理对于每个格子朝着某个方向移动一步所需要的步数，作为前后两个状态的边权，最后用最短路OK。。。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int INF=~0U>>2;
int n,m,q,V;
int Map[35][35],A[35][35][4];
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct Point
{
int x,y;
inline bool operator==(const Point& X)
{
return X.x==this->x && X.y==this->y;
}
inline bool operator!=(const Point& X)
{
return X.x!=this->x||X.y!=this->y;
}
Point(int X=0,int Y=0):x(X),y(Y){}
inline void Read()
{
scanf("%d%d",&x,&y);
}
};
bool Vst[35][35];
int Dis[35][35];
queue<Point> Q;
int Bfs(const Point& S,const Point& T,const Point& K)
{
while (!Q.empty()) Q.pop();
memset(Vst,false,sizeof(Vst));
Q.push(S);
Vst[S.x][S.y]=true,Dis[S.x][S.y]=0;
while (!Q.empty())
{
Point C=Q.front();
Q.pop();
if (C==T) return Dis[T.x][T.y];
for (int i=0;i<4;i++)
if (Map[C.x+dx[i]][C.y+dy[i]] && !Vst[C.x+dx[i]][C.y+dy[i]] && Point(C.x+dx[i],C.y+dy[i])!=K)
{
Dis[C.x+dx[i]][C.y+dy[i]]=Dis[C.x][C.y]+1;
Vst[C.x+dx[i]][C.y+dy[i]]=true;
Q.push(Point(C.x+dx[i],C.y+dy[i]));
}
}
return INF;
}
int son[35*35*4],Ecnt,Ans[35*35*4];
bool inq[35*35*4];
struct Edge
{
int link,next,cost;
}ed[35*35*4*50];
inline void Add(int u,int v,int c)
{
ed[++Ecnt].link=v,ed[Ecnt].next=son[u],son[u]=Ecnt;
ed[Ecnt].cost=c;
}
queue<int> Qw;
struct sit
{
int x,y,p;
inline void Cov(int X,int Y,int P)
{
x=X,y=Y,p=P;
}
}Ch[35*35*4];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",Map[i]+j);
for (int k=0;k<4;k++)
A[i][j][k]=++V,Ch[V].Cov(i,j,k);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (Map[i][j])
for (int k=0;k<4;k++)
if (Map[i+dx[k]][j+dy[k]])
Add(A[i][j][k],A[i+dx[k]][j+dy[k]][k^1],1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (Map[i][j])
for (int k=0;k<4;k++)
if (Map[i+dx[k]][j+dy[k]])
for (int l=0;l<4;l++)
if (l!=k && Map[i+dx[l]][j+dy[l]])
Add(A[i][j][k],A[i][j][l],Bfs(Point(i+dx[k],j+dy[k]),Point(i+dx[l],j+dy[l]),Point(i,j)));
Point E,S,T;
while (q--)
{
memset(inq,false,sizeof(inq));
while (!Qw.empty()) Qw.pop();
E.Read(),S.Read(),T.Read();
if (Map[S.x][S.y]==0 || Map[E.x][E.y]==0 || Map[T.x][T.y]==0 || E==S)
{
puts("-1");
continue;
}
if(S==T)
{
puts("0");
continue;
}
for (int i=1;i<=V;i++) Ans[i]=INF;
for (int i=0;i<4;i++)
if (Map[S.x+dx[i]][S.y+dy[i]])
{
int D=Bfs(E,Point(S.x+dx[i],S.y+dy[i]),S);
if (D!=INF)
{
Qw.push(A[S.x][S.y][i]);
Ans[A[S.x][S.y][i]]=D;
inq[A[S.x][S.y][i]]=true;
}
}
while (!Qw.empty())
{
int C=Qw.front();
inq[C]=false;
Qw.pop();
for (int i=son[C];i;i=ed[i].next)
if (Ans[C]+ed[i].cost<Ans[ed[i].link])
{
Ans[ed[i].link]=Ans[C]+ed[i].cost;
if (!inq[ed[i].link])
{
Qw.push(ed[i].link);
inq[ed[i].link]=true;
}
}
}
int res=INF;
for (int i=0;i<4;i++)
if (Map[T.x+dx[i]][T.y+dy[i]] && Ans[A[T.x][T.y][i]]<res) res=Ans[A[T.x][T.y][i]];
if (res==INF) puts("-1");
else printf("%d\n",res);
}
return 0;
}

const
inf=maxlongint>>1;
go:array[0..3,1..2]of longint=((-1,0),(1,0),(0,-1),(0,1));
var
n,m,q,i,j,l,k,h,t,stx,sty,enx,eny,kx,ky,ans:longint;
a:array[0..31,0..31]of longint;
d:array[1..100000,1..3]of longint;
short:array[1..30,1..30,0..3,1..30,1..30]of longint;
g:array[1..30,1..30]of longint;
f:array[1..30,1..30,0..3]of longint;
ok:array[1..30,1..30,0..3]of boolean;
begin

readln(n,m,q);
for i:=1 to n do
begin
for j:=1 to m do read(a[i,j]);
readln;
end;
for i:=1 to n do
for j:=1 to m do
if a[i,j]=1 then
begin
a[i,j]:=0;
for l:=0 to 3 do
if a[i+go[l,1],j+go[l,2]]=1 then
begin
fillchar(short[i,j,l],sizeof(short[i,j,l]),127);
h:=0;
t:=1;
d[1,1]:=i+go[l,1];
d[1,2]:=j+go[l,2];
short[i,j,l,d[1,1],d[1,2]]:=0;
while h<t do
begin
inc(h);
for k:=0 to 3 do
if (a[d[h,1]+go[k,1],d[h,2]+go[k,2]]=1)and(short[i,j,l,d[h,1]+go[k,1],d[h,2]+go[k,2]]>short[i,j,l,d[h,1],d[h,2]]+1) then
begin
inc(t);
d[t,1]:=d[h,1]+go[k,1];
d[t,2]:=d[h,2]+go[k,2];
short[i,j,l,d[t,1],d[t,2]]:=short[i,j,l,d[h,1],d[h,2]]+1;
end;
end;
end;
a[i,j]:=1;
end;
for l:=1 to q do
begin
readln(kx,ky,stx,sty,enx,eny);
a[stx,sty]:=0;
fillchar(g,sizeof(g),127);
g[kx,ky]:=0;
h:=0;
t:=1;
d[1,1]:=kx;
d[1,2]:=ky;
while h<t do
begin
inc(h);
for k:=0 to 3 do
if (a[d[h,1]+go[k,1],d[h,2]+go[k,2]]=1)and(g[d[h,1]+go[k,1],d[h,2]+go[k,2]]>g[d[h,1],d[h,2]]+1) then
begin
inc(t);
d[t,1]:=d[h,1]+go[k,1];
d[t,2]:=d[h,2]+go[k,2];
g[d[t,1],d[t,2]]:=g[d[h,1],d[h,2]]+1;
end;
end;
a[stx,sty]:=1;
h:=0;
t:=0;
fillchar(f,sizeof(f),127);
fillchar(ok,sizeof(ok),1);
f[stx,sty,0]:=0;
f[stx,sty,1]:=0;
f[stx,sty,2]:=0;
f[stx,sty,3]:=0;
for k:=0 to 3 do
if (a[stx+go[k,1],sty+go[k,2]]=1)and(g[stx+go[k,1],sty+go[k,2]]<inf) then
begin
inc(t);
d[t,1]:=stx+go[k,1];
d[t,2]:=sty+go[k,2];
d[t,3]:=k xor 1;
f[d[t,1],d[t,2],d[t,3]]:=g[d[t,1],d[t,2]]+1;
ok[d[t,1],d[t,2],d[t,3]]:=false;
end;
while h<t do
begin
inc(h);
for k:=0 to 3 do
if (a[d[h,1]+go[k,1],d[h,2]+go[k,2]]=1)and(short[d[h,1],d[h,2],d[h,3],d[h,1]+go[k,1],d[h,2]+go[k,2]]<inf) then
if f[d[h,1]+go[k,1],d[h,2]+go[k,2],k xor 1]>f[d[h,1],d[h,2],d[h,3]]+short[d[h,1],d[h,2],d[h,3],d[h,1]+go[k,1],d[h,2]+go[k,2]]+1 then
begin
f[d[h,1]+go[k,1],d[h,2]+go[k,2],k xor 1]:=f[d[h,1],d[h,2],d[h,3]]+short[d[h,1],d[h,2],d[h,3],d[h,1]+go[k,1],d[h,2]+go[k,2]]+1;
if ok[d[h,1]+go[k,1],d[h,2]+go[k,2],k xor 1] then
begin
inc(t);
d[t,1]:=d[h,1]+go[k,1];
d[t,2]:=d[h,2]+go[k,2];
d[t,3]:=k xor 1;
ok[d[t,1],d[t,2],d[t,3]]:=false;
end;
end;
ok[d[h,1],d[h,2],d[h,3]]:=true;
end;
ans:=inf;
if f[enx,eny,0]<ans then ans:=f[enx,eny,0];
if f[enx,eny,1]<ans then ans:=f[enx,eny,1];
if f[enx,eny,2]<ans then ans:=f[enx,eny,2];
if f[enx,eny,3]<ans then ans:=f[enx,eny,3];
if ans=inf then writeln(-1)
else writeln(ans);
end;

end.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN 32
#define MAXV 50010
#define inf (1<<26)

const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

struct edge {
edge *next;
int t,d;
edge () {
next=NULL;
}
} *head[MAXV];

void AddEdge(int s,int t,int d) {
edge *p=new(edge);
p->t=t,p->d=d;
p->next=head[s];
head[s]=p;
}

int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty;
int v[MAXN][MAXN][4],V=0;
int dist[MAXN][MAXN],Move[MAXN][MAXN][4][4];

int Dist[MAXV];
bool f[MAXV];

int S,T;

struct node {
int x,y;
node (int _x,int _y):x(_x),y(_y) {

}
};
queue<node>Q;

int Bfs(int Sx,int Sy,int Tx,int Ty) {
if (Sx==Tx&&Sy==Ty) return 0;
while (!Q.empty()) Q.pop();
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
dist[i][j]=inf;
}
}
dist[Sx][Sy]=0;
Q.push(node(Sx,Sy));
while (!Q.empty()) {
node u=Q.front();
Q.pop();
for (int i=0;i<4;i++) {
if (Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf) {
dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;
if (u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty) return dist[u.x][u.y]+1;
Q.push(node(u.x+dir[i][0],u.y+dir[i][1]));
}
}
}
return inf;
}

queue<int>Pq;

int spfa() {
for (int i=0;i++<V;) Dist[i]=inf;
memset(f,true,sizeof(f));
while (!Pq.empty()) Pq.pop();
Dist[S]=0;
Pq.push(S);
while (!Pq.empty()) {
int u=Pq.front();
Pq.pop();
if (!f[u]) continue;
f[u]=false;
for (edge *p=head[u];p;p=p->next) {
if (Dist[p->t]>Dist[u]+p->d) {
Dist[p->t]=Dist[u]+p->d;
f[p->t]=true;
Pq.push(p->t);
}
}
}
return Dist[T]<inf?Dist[T]:-1;
}

int main() {
cin>>n>>m>>q;
memset(Map,0,sizeof(Map));
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
cin>>Map[i][j];
for (int k=0;k<4;k++) {
v[i][j][k]=++V;
}
}
}
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
for (int k=0;k<4;k++) {
for (int h=0;h<4;h++) {
Move[i][j][k][h]=inf;
}
}
}
}
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
if (Map[i][j]) {
Map[i][j]=0;
for (int k=0;k<4;k++) {
if (Map[i+dir[k][0]][j+dir[k][1]]) {
for (int h=0;h<4;h++) {
if (Map[i+dir[h][0]][j+dir[h][1]]) {
Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1;
}
}
}
}
Map[i][j]=1;
}
}
}
memset(head,0,sizeof(head));
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
for (int k=0;k<4;k++) {
for (int h=0;h<4;h++) {
if (Move[i][j][k][h]<inf) {
AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]);
}
}
}
}
}
while (q--) {
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if (sx==tx&&sy==ty) {
cout<<0<<endl;
continue;
}
S=++V;
T=++V;
if (Map[sx][sy]==0||Map[tx][ty]==0) {
cout<<-1<<endl;
continue;
}
Map[sx][sy]=0;
for (int i=0;i<4;i++) {
if (Map[sx+dir[i][0]][sy+dir[i][1]]) {
int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]);
if (D<inf) {
AddEdge(S,v[sx][sy][i],D);
}
}
}
Map[sx][sy]=1;
for (int i=0;i<4;i++) {
if (Map[tx+dir[i][0]][ty+dir[i][1]]) {
AddEdge(v[tx][ty][i],T,0);
}
}
cout<<spfa()<<endl;
}
return 0;
}

const
u:array[1..4] of integer=(-1,0,1,0);

v:array[1..4] of integer=(0,1,0,-1);

oo=100000000;

var
ft:text;

n,m,q,ii,i,i1,j1,j,l,w,x,y,x1,y1,x2,y2,x3,y3,es,ey,wei,tou,kx,ky,ans:longint;

r:array[0..5000000] of record
x,y,cs,l:longint;

end;

aa,a,fb,fb2:array[0..31,0..31] of longint;

ff,z,z2:array[0..31,0..31,1..4] of longint;

f:array[0..31,0..31,1..4,1..4] of longint;

procedure bfs(x,y:longint);

var
i,x1,y1:longint;

begin
wei:=1;

tou:=0;

r[wei].x:=x;

r[wei].y:=y;

r[wei].cs:=fb[x,y];

while tou<wei do
begin
inc(tou);
for i:=1 to 4 do
begin
x1:=r[tou].x+u[i];
y1:=r[tou].y+v[i];
if (a[x1,y1]=1)and(r[tou].cs+1<fb[x1,y1]) then
begin
inc(wei);
r[wei].x:=x1;
r[wei].y:=y1;
r[wei].cs:=r[tou].cs+1;
fb[x1,y1]:=r[wei].cs;
end;
end;
end;
end;
begin
readln(n,m,q);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
aa:=a;
for i:=1 to n do
for j:=1 to m do
begin
fb2[i,j]:=oo;
for l:=1 to 4 do
begin
z2[i,j,l]:=oo;
for w:=1 to 4 do f[i,j,l,w]:=oo;
end;
end;
for i:=1 to n do
for j:=1 to m do
if a[i,j]=1 then
for l:=1 to 4 do
begin
x:=i+u[l];
y:=j+v[l];
if (x>0)and(x<n+1)and(y>0)and(y<m+1)and(a[x,y]=1) then
begin
a[x,y]:=0;
fb:=fb2;
fb[i,j]:=1;
bfs(i,j);
for w:=1 to 4 do
begin
x1:=x+u[w];
y1:=y+v[w];
if (x1>0)and(x1<n+1)and(y1>0)and(y1<m+1)and(fb[x1,y1]<oo) then
begin
f[i,j,l,w]:=fb[x1,y1];
end;
end;
a[x,y]:=1;
end;
end;
for ii:=1 to q do
begin
read(kx,ky,x,y,es,ey);
if (x=es)and(y=ey) then
begin
writeln(0);
continue;
end;
fb:=fb2;
a[x,y]:=0;
fb[kx,ky]:=0;
bfs(kx,ky);
wei:=0;
z:=z2;
fillchar(ff,sizeof(ff),0);
for j:=1 to 4 do
begin
x1:=x+u[j];
y1:=y+v[j];
if (x1>0)and(x1<n+1)and(y1>0)and(y1<m+1)and(fb[x1,y1]<oo) then
begin
inc(wei);
r[wei].x:=x;
r[wei].y:=y;
r[wei].l:=j;
z[x,y,j]:=fb[x1,y1];
ff[x,y,j]:=1;
end;
end;
tou:=0;
while tou<wei do
begin
inc(tou);
for i:=1 to 4 do
begin
x2:=r[tou].x;
y2:=r[tou].y;
x1:=x2+u[r[tou].l]+u[i];
y1:=y2+v[r[tou].l]+v[i];
x3:=x2+u[r[tou].l];
y3:=y2+v[r[tou].l];
if (f[x2,y2,r[tou].l,i]<>oo)and(z[x3,y3,i]>z[x2,y2,r[tou].l]+f[x2,y2,r[tou].l,i]) then
begin
z[x3,y3,i]:=z[x2,y2,r[tou].l]+f[x2,y2,r[tou].l,i];

if ff[x3,y3,i]=0 then
begin
ff[x3,y3,i]:=1;

inc(wei);

r[wei].x:=x3;

r[wei].y:=y3;

r[wei].l:=i;

end;

end;

end;

ff[r[tou].x,r[tou].y,r[tou].l]:=0;

end;

ans:=oo;

for i:=1 to 4 do
if z[es,ey,i]<ans then ans:=z[es,ey,i];

if ans=oo then writeln(-1) else writeln(ans);

a[x,y]:=1;

end;

end.

说白了就是这样。。。。。。（非原创）
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 32
#define MAXV 50010
#define inf (1<<26)
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct edge{
edge *next;
int t,d;
edge (){
next=NULL;
}
}*head[MAXV];
void AddEdge(int s,int t,int d){
edge *p=new(edge);
p->t=t,p->d=d;
p->next=head[s];
head[s]=p;
}
int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty,v[MAXN][MAXN][4],V=0,dist[MAXN][MAXN],Move[MAXN][MAXN][4][4],Dist[MAXV];
bool f[MAXV];
int S,T;
struct node{
int x,y;
node (int _x,int _y):x(_x),y(_y){}
};
queue<node>Q;
int Bfs(int Sx,int Sy,int Tx,int Ty){
if(Sx==Tx&&Sy==Ty)return 0;
while(!Q.empty()) Q.pop();
for(int i=0;i++<n;) for(int j=0;j++<m;)dist[i][j]=inf;
dist[Sx][Sy]=0;
Q.push(node(Sx,Sy));
while(!Q.empty()){
node u=Q.front();
Q.pop();
for(int i=0;i<4;i++){
if(Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf){
dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;
if(u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty)return dist[u.x][u.y]+1;
Q.push(node(u.x+dir[i][0],u.y+dir[i][1]));
}
}
}
return inf;
}
struct Cmp{
bool operator()(int x,int y){
return Dist[x]>Dist[y];
}
};
priority_queue<int,vector<int>,Cmp>Pq;
int spfa(){
for(int i=0;i++<V;)Dist[i]=inf;
memset(f,true,sizeof(f));
while(!Pq.empty()) Pq.pop();
Dist[S]=0;
Pq.push(S);
while(!Pq.empty()){
int u=Pq.top();
Pq.pop();
if(!f[u])continue;
f[u]=false;
if(u==T)return Dist[T];
for(edge *p=head[u];p;p=p->next){
if(Dist[p->t]>Dist[u]+p->d){
Dist[p->t]=Dist[u]+p->d;
f[p->t]=true;
Pq.push(p->t);
}
}
}
return Dist[T]<inf?Dist[T]:-1;
}
int main(){
cin>>n>>m>>q;
memset(Map,0,sizeof(Map));
for(int i=0;i++<n;){
for(int j=0;j++<m;){
cin>>Map[i][j];
for(int k=0;k<4;k++){
v[i][j][k]=++V;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
for(int k=0;k<4;k++){
for(int h=0;h<4;h++)Move[i][j][k][h]=inf;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
if(Map[i][j]){
Map[i][j]=0;
for(int k=0;k<4;k++){
if(Map[i+dir[k][0]][j+dir[k][1]]){
for(int h=0;h<4;h++){
if(Map[i+dir[h][0]][j+dir[h][1]]){
Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1;
}
}
}
}
Map[i][j]=1;
}
}
}
memset(head,0,sizeof(head));
for(int i=0;i++<n;) for(int j=0;j++<m;) for(int k=0;k<4;k++)for(int h=0;h<4;h++)
if(Move[i][j][k][h]<inf)AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]);
while(q--){
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){ cout<<0<<endl;continue;}
S=++V; T=++V;
if(Map[sx][sy]==0||Map[tx][ty]==0){cout<<-1<<endl; continue; }
Map[sx][sy]=0;
for(int i=0;i<4;i++){
if(Map[sx+dir[i][0]][sy+dir[i][1]]){
int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]);
if(D<inf)AddEdge(S,v[sx][sy][i],D);
}
}
Map[sx][sy]=1;
for(int i=0;i<4;i++) if(Map[tx+dir[i][0]][ty+dir[i][1]])AddEdge(v[tx][ty][i],T,0);
cout<<spfa()<<endl;
}
return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 32
#define MAXV 50010
#define inf (1<<26)
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct edge{
edge *next;
int t,d;
edge (){
next=NULL;
}
}*head[MAXV];
void AddEdge(int s,int t,int d){
edge *p=new(edge);
p->t=t,p->d=d;
p->next=head[s];
head[s]=p;
}
int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty,v[MAXN][MAXN][4],V=0,dist[MAXN][MAXN],Move[MAXN][MAXN][4][4],Dist[MAXV];
bool f[MAXV];
int S,T;
struct node{
int x,y;
node (int _x,int _y):x(_x),y(_y){}
};
queue<node>Q;
int Bfs(int Sx,int Sy,int Tx,int Ty){
if(Sx==Tx&&Sy==Ty)return 0;
while(!Q.empty()) Q.pop();
for(int i=0;i++<n;) for(int j=0;j++<m;)dist[i][j]=inf;
dist[Sx][Sy]=0;
Q.push(node(Sx,Sy));
while(!Q.empty()){
node u=Q.front();
Q.pop();
for(int i=0;i<4;i++){
if(Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf){
dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;
if(u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty)return dist[u.x][u.y]+1;
Q.push(node(u.x+dir[i][0],u.y+dir[i][1]));
}
}
}
return inf;
}
struct Cmp{
bool operator()(int x,int y){
return Dist[x]>Dist[y];
}
};
priority_queue<int,vector<int>,Cmp>Pq;
int spfa(){
for(int i=0;i++<V;)Dist[i]=inf;
memset(f,true,sizeof(f));
while(!Pq.empty()) Pq.pop();
Dist[S]=0;
Pq.push(S);
while(!Pq.empty()){
int u=Pq.top();
Pq.pop();
if(!f[u])continue;
f[u]=false;
if(u==T)return Dist[T];
for(edge *p=head[u];p;p=p->next){
if(Dist[p->t]>Dist[u]+p->d){
Dist[p->t]=Dist[u]+p->d;
f[p->t]=true;
Pq.push(p->t);
}
}
}
return Dist[T]<inf?Dist[T]:-1;
}
int main(){
cin>>n>>m>>q;
memset(Map,0,sizeof(Map));
for(int i=0;i++<n;){
for(int j=0;j++<m;){
cin>>Map[i][j];
for(int k=0;k<4;k++){
v[i][j][k]=++V;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
for(int k=0;k<4;k++){
for(int h=0;h<4;h++)Move[i][j][k][h]=inf;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
if(Map[i][j]){
Map[i][j]=0;
for(int k=0;k<4;k++){
if(Map[i+dir[k][0]][j+dir[k][1]]){
for(int h=0;h<4;h++){
if(Map[i+dir[h][0]][j+dir[h][1]]){
Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1;
}
}
}
}
Map[i][j]=1;
}
}
}
memset(head,0,sizeof(head));
for(int i=0;i++<n;) for(int j=0;j++<m;) for(int k=0;k<4;k++)for(int h=0;h<4;h++)
if(Move[i][j][k][h]<inf)AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]);
while(q--){
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){ cout<<0<<endl;continue;}
S=++V; T=++V;
if(Map[sx][sy]==0||Map[tx][ty]==0){cout<<-1<<endl; continue; }
Map[sx][sy]=0;
for(int i=0;i<4;i++){
if(Map[sx+dir[i][0]][sy+dir[i][1]]){
int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]);
if(D<inf)AddEdge(S,v[sx][sy][i],D);
}
}
Map[sx][sy]=1;
for(int i=0;i<4;i++) if(Map[tx+dir[i][0]][ty+dir[i][1]])AddEdge(v[tx][ty][i],T,0);
cout<<spfa()<<endl;
}
return 0;
}

预处理+最短路：
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 1128 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 1128 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 1128 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 1136 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 1132 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 1132 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 1476 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 1488 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 1484 KiB, score = 5
测试数据 #9: Accepted, time = 46 ms, mem = 1500 KiB, score = 5
测试数据 #10: Accepted, time = 31 ms, mem = 1356 KiB, score = 5
测试数据 #11: Accepted, time = 46 ms, mem = 1368 KiB, score = 5
测试数据 #12: Accepted, time = 171 ms, mem = 1520 KiB, score = 5
测试数据 #13: Accepted, time = 156 ms, mem = 1476 KiB, score = 5
测试数据 #14: Accepted, time = 156 ms, mem = 1468 KiB, score = 5
测试数据 #15: Accepted, time = 156 ms, mem = 1460 KiB, score = 5
测试数据 #16: Accepted, time = 171 ms, mem = 1496 KiB, score = 5
测试数据 #17: Accepted, time = 171 ms, mem = 1516 KiB, score = 5
测试数据 #18: Accepted, time = 171 ms, mem = 1488 KiB, score = 5
测试数据 #19: Accepted, time = 218 ms, mem = 1776 KiB, score = 5
Accepted, time = 1646 ms, mem = 1776 KiB, score = 100

点此查看题解及代码

测试数据 #0: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 79128 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 79136 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 79136 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 79136 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 79132 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #10: Accepted, time = 15 ms, mem = 79128 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 79132 KiB, score = 5
测试数据 #12: Accepted, time = 15 ms, mem = 79132 KiB, score = 5
测试数据 #13: Accepted, time = 31 ms, mem = 79132 KiB, score = 5
测试数据 #14: Accepted, time = 46 ms, mem = 79132 KiB, score = 5
测试数据 #15: Accepted, time = 78 ms, mem = 79128 KiB, score = 5
测试数据 #16: Accepted, time = 31 ms, mem = 79128 KiB, score = 5
测试数据 #17: Accepted, time = 31 ms, mem = 79132 KiB, score = 5
测试数据 #18: Accepted, time = 46 ms, mem = 79132 KiB, score = 5
测试数据 #19: Accepted, time = 46 ms, mem = 79132 KiB, score = 5
Accepted, time = 369 ms, mem = 79136 KiB, score = 100

发个有缩进的代码吧：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN 32
#define MAXV 50010
#define inf (1<<26)

const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

struct edge {
edge *next;
int t,d;
edge () {
next=NULL;
}
} *head[MAXV];

void AddEdge(int s,int t,int d) {
edge *p=new(edge);
p->t=t,p->d=d;
p->next=head[s];
head[s]=p;
}

int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty;
int v[MAXN][MAXN][4],V=0;
int dist[MAXN][MAXN],Move[MAXN][MAXN][4][4];

int Dist[MAXV];
bool f[MAXV];

int S,T;

struct node {
int x,y;
node (int _x,int _y):x(_x),y(_y) {

}
};
queue<node>Q;

int Bfs(int Sx,int Sy,int Tx,int Ty) {
if (Sx==Tx&&Sy==Ty) return 0;
while (!Q.empty()) Q.pop();
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
dist[i][j]=inf;
}
}
dist[Sx][Sy]=0;
Q.push(node(Sx,Sy));
while (!Q.empty()) {
node u=Q.front();
Q.pop();
for (int i=0;i<4;i++) {
if (Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf) {
dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;
if (u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty) return dist[u.x][u.y]+1;
Q.push(node(u.x+dir[i][0],u.y+dir[i][1]));
}
}
}
return inf;
}

queue<int>Pq;

int spfa() {
for (int i=0;i++<V;) Dist[i]=inf;
memset(f,true,sizeof(f));
while (!Pq.empty()) Pq.pop();
Dist[S]=0;
Pq.push(S);
while (!Pq.empty()) {
int u=Pq.front();
Pq.pop();
if (!f[u]) continue;
f[u]=false;
for (edge *p=head[u];p;p=p->next) {
if (Dist[p->t]>Dist[u]+p->d) {
Dist[p->t]=Dist[u]+p->d;
f[p->t]=true;
Pq.push(p->t);
}
}
}
return Dist[T]<inf?Dist[T]:-1;
}

int main() {
cin>>n>>m>>q;
memset(Map,0,sizeof(Map));
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
cin>>Map[i][j];
for (int k=0;k<4;k++) {
v[i][j][k]=++V;
}
}
}
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
for (int k=0;k<4;k++) {
for (int h=0;h<4;h++) {
Move[i][j][k][h]=inf;
}
}
}
}
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
if (Map[i][j]) {
Map[i][j]=0;
for (int k=0;k<4;k++) {
if (Map[i+dir[k][0]][j+dir[k][1]]) {
for (int h=0;h<4;h++) {
if (Map[i+dir[h][0]][j+dir[h][1]]) {
Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1;
}
}
}
}
Map[i][j]=1;
}
}
}
memset(head,0,sizeof(head));
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
for (int k=0;k<4;k++) {
for (int h=0;h<4;h++) {
if (Move[i][j][k][h]<inf) {
AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]);
}
}
}
}
}
while (q--) {
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if (sx==tx&&sy==ty) {
cout<<0<<endl;
continue;
}
S=++V;
T=++V;
if (Map[sx][sy]==0||Map[tx][ty]==0) {
cout<<-1<<endl;
continue;
}
Map[sx][sy]=0;
for (int i=0;i<4;i++) {
if (Map[sx+dir[i][0]][sy+dir[i][1]]) {
int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]);
if (D<inf) {
AddEdge(S,v[sx][sy][i],D);
}
}
}
Map[sx][sy]=1;
for (int i=0;i<4;i++) {
if (Map[tx+dir[i][0]][ty+dir[i][1]]) {
AddEdge(v[tx][ty][i],T,0);
}
}
cout<<spfa()<<endl;
}
return 0;
}