由于不太会打bfs，这题用的dfs。
通过这道题还是学到了蛮多的东西的。
首先，瞎打一气（dfs + 标记走过的点）40分。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int X[] = {,,,-};
const int Y[] = {,,-,};
int m,n,ex,ey,a,b,c,d,ans,used[][][][],ma[][],q;
bool can(int x,int y)
{
if(x < ||x > n) return false;
if(y < ||y > m) return false;
if(!ma[x][y]) return false;
return true;
}
void dfs(int kx,int ky,int sx,int sy,int cnt)
{
if(cnt >= ans) return;
if(sx == ex&&sy == ey) {ans = cnt;return;}
if(used[kx][ky][sx][sy] <= cnt) return;
used[kx][ky][sx][sy] = cnt;
for(int i = ;i < ;i ++)
{
int x = kx + X[i],y = ky + Y[i];
if(can(x,y))
{
if(x == sx&&y == sy) dfs(x,y,kx,ky,cnt+);
else dfs(x,y,sx,sy,cnt+);
}
}
}
int main()
{
scanf("%d %d %d",&n,&m,&q);
for(int i = ;i <= n;i ++)
for(int j = ;j <= m;j ++)
scanf("%d",&ma[i][j]);
for(int i = ;i <= q;i ++)
{
memset(used,,sizeof(used));ans = ;
scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,);
if(ans == ) puts("-1");
else printf("%d\n",ans);
}
}
然后发现这个题没有办法剪枝，如果不标记路线会死循环，如果标记就没有办法记忆化搜索。
然后仔细观察了之前的程序，发现每一次起点走了一步，空位就要跑完整张图，而我们的目的是让起点移动到终点。所以我们只要让起点移动就可以了。
过程为，空格移动到起点的旁边，起点启动到空格，并且在这个过程中，空格不能经过起点。
所以我们要预处理一下，计算从a 点到b点不经过c点的最短距离，这个预处理的复杂度是O（n^6）的，这样会超时。
我们再考虑一下，起点和起点将要移动的位置一定是挨着的。因此我们只需要处理某一个点不经过上下左右4点然后反向找从起点将要移动的点不经过起点到空格的位置（4*n^4）。
85分代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int X[] = {,,,-};
const int Y[] = {,,-,};
int n,m,g,ma[][],dis[][][][][],used[][],ans,a,b,c,d,ex,ey,vis[][][][];
struct zt
{
int x,y;
};
queue<zt>q;
bool can(int x,int y)
{
if(x < ||x > n) return false;
if(y < ||y > m) return false;
if(!ma[x][y]) return false;
return true;
}
void spfa(int x,int y,int nx,int ny,int ji)
{
while(!q.empty()) q.pop();
memset(used,,sizeof(used));
q.push((zt){x,y});
dis[x][y][x][y][ji] = ;
while(!q.empty())
{
zt u = q.front();q.pop();
used[u.x][u.y] = ;
for(int i = ;i < ;i ++)
{
int x1 = u.x + X[i],y1 = u.y + Y[i];
if(can(x1,y1)&&(x1 != nx||y1 != ny))
{
if(dis[x][y][x1][y1][ji] > dis[x][y][u.x][u.y][ji] + )
{
dis[x][y][x1][y1][ji] = dis[x][y][u.x][u.y][ji] + ;
if(!used[x1][y1])
{
q.push((zt){x1,y1});
used[x1][y1] = ;
}
}
}
}
}
}
void dfs(int kx,int ky,int sx,int sy,int cnt)
{
if(cnt >= ans) return;
if(sx == ex&&sy == ey) {ans = cnt;return;}
if(vis[sx][sy][kx][ky] <= cnt) return;
vis[sx][sy][kx][ky] = cnt;
for(int i = ;i < ;i ++)
{
int x = sx + X[i],y = sy + Y[i];
if(can(x,y))
dfs(sx,sy,x,y,cnt+dis[x][y][kx][ky][(i+)%]+);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&g);
for(int i = ;i <= n;i ++)
for(int j = ;j <= m;j ++)
scanf("%d",&ma[i][j]);
memset(dis,,sizeof(dis));
for(int i = ;i <= n;i ++)
for(int j = ;j <= m;j ++)
{
if(!ma[i][j]) continue;
for(int k = ;k < ;k ++)
{
a = i + X[k],b = j + Y[k];
if(can(a,b)) spfa(i,j,a,b,k);
}
}
for(int i = ;i <= g;i ++)
{
memset(vis,,sizeof(vis));ans = ;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,);
if(ans == ) puts("-1");
else printf("%d\n",ans);
}
}
然后我们会发现将数组vis赋为极大值的复杂度是（500*35^4 = 750312500）。
这样对于后面的点，单是初始化就不够用了。
我们再观察一下，发现除未开始移动时，空位一定在起点四周。这样我们只要开一个大小为5的数组代替就可以。这样初始化为（500 * 35^2 * 5 = 3062500）。
这样做后会有90分。
这里再引入一个东西——启发式搜索。
启发式搜索会极大地减少重复经过的路径从而提高dfs的效率。简单说我们优先更新付出代价比较小的状态，这样这个状态就很难被再次更新，从而减少不必要的步骤。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int X[] = {,,,-};
const int Y[] = {,,-,};
int n,m,g,ma[][],dis[][][][][],used[][],ans,a,b,c,d,ex,ey,vis[][][];
struct zt
{
int x,y;
};
queue<zt>q;
bool can(int x,int y)
{
if(x < ||x > n) return false;
if(y < ||y > m) return false;
if(!ma[x][y]) return false;
return true;
}
void spfa(int x,int y,int nx,int ny,int ji)
{
while(!q.empty()) q.pop();
memset(used,,sizeof(used));
q.push((zt){x,y});
dis[x][y][x][y][ji] = ;
while(!q.empty())
{
zt u = q.front();q.pop();
used[u.x][u.y] = ;
for(int i = ;i < ;i ++)
{
int x1 = u.x + X[i],y1 = u.y + Y[i];
if(can(x1,y1)&&(x1 != nx||y1 != ny))
{
if(dis[x][y][x1][y1][ji] > dis[x][y][u.x][u.y][ji] + )
{
dis[x][y][x1][y1][ji] = dis[x][y][u.x][u.y][ji] + ;
if(!used[x1][y1])
{
q.push((zt){x1,y1});
used[x1][y1] = ;
}
}
}
}
}
}
void dfs(int kx,int ky,int sx,int sy,int cnt,int k)
{
if(cnt >= ans) return;
if(sx == ex&&sy == ey) {ans = cnt;return;}
if(vis[sx][sy][k] <= cnt) return;
vis[sx][sy][k] = cnt;
int used2[] = {,,,},ji,lu;
for(int i = ;i < ;i ++)
{
lu = ;
for(int j = ;j < ;j ++)
{
int x = sx + X[j],y = sy + Y[j];
if(can(x,y)&&lu > dis[x][y][kx][ky][(j+)%]&&!used2[j])
lu = dis[x][y][kx][ky][(j+)%],ji = j;
}
if(lu != )
{
int x = sx + X[ji],y = sy + Y[ji];used2[ji] = ;
dfs(sx,sy,x,y,cnt+dis[x][y][kx][ky][(ji+)%]+,(ji+)%);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&g);
for(int i = ;i <= n;i ++)
for(int j = ;j <= m;j ++)
scanf("%d",&ma[i][j]);
memset(dis,,sizeof(dis));
for(int i = ;i <= n;i ++)
for(int j = ;j <= m;j ++)
{
if(!ma[i][j]) continue;
for(int k = ;k < ;k ++)
{
a = i + X[k],b = j + Y[k];
if(can(a,b)) spfa(i,j,a,b,k);
}
}
for(int i = ;i <= g;i ++)
{
memset(vis,,sizeof(vis));ans = ;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,,);
if(ans == ) puts("-1");
else printf("%d\n",ans);
}
}
![tarjan算法介绍与分析[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)