题解 P1979 【华容道 】
这道题没有人发dfs，发个题解
由于不太会打bfs，这题用的dfs。
通过这道题还是学到了蛮多的东西的。
首先，瞎打一气（dfs + 标记走过的点）40分。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int X[] = {0,1,0,-1};
const int Y[] = {1,0,-1,0};
int m,n,ex,ey,a,b,c,d,ans,used[45][45][45][45],ma[50][50],q;
bool can(int x,int y)
{
if(x < 1||x > n) return false;
if(y < 1||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 = 0;i < 4;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+1);
else dfs(x,y,sx,sy,cnt+1);
}
}
}
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",&ma[i][j]);
for(int i = 1;i <= q;i ++)
{
memset(used,0x3f,sizeof(used));ans = 1e6;
scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,0);
if(ans == 1e6) puts("-1");
else printf("%d\n",ans);
}
}1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 然后发现这个题没有办法剪枝，如果不标记路线会死循环，如果标记就没有办法记忆化搜索。
然后仔细观察了之前的程序，发现每一次起点走了一步，空位就要跑完整张图，而我们的目的是让起点移动到终点。所以我们只要让起点移动就可以了。
过程为，空格移动到起点的旁边，起点启动到空格，并且在这个过程中，空格不能经过起点。
所以我们要预处理一下，计算从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[] = {0,1,0,-1};
const int Y[] = {1,0,-1,0};
int n,m,g,ma[35][35],dis[35][35][35][35][5],used[35][35],ans,a,b,c,d,ex,ey,vis[35][35][35][35];
struct zt
{
int x,y;
};
queue<zt>q;
bool can(int x,int y)
{
if(x < 1||x > n) return false;
if(y < 1||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,0,sizeof(used));
q.push((zt){x,y});
dis[x][y][x][y][ji] = 0;
while(!q.empty())
{
zt u = q.front();q.pop();
used[u.x][u.y] = 0;
for(int i = 0;i < 4;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] + 1)
{
dis[x][y][x1][y1][ji] = dis[x][y][u.x][u.y][ji] + 1;
if(!used[x1][y1])
{
q.push((zt){x1,y1});
used[x1][y1] = 1;
}
}
}
}
}
}
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 = 0;i < 4;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+2)%4]+1);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&g);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
scanf("%d",&ma[i][j]);
memset(dis,0x3f,sizeof(dis));
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
if(!ma[i][j]) continue;
for(int k = 0;k < 4;k ++)
{
a = i + X[k],b = j + Y[k];
if(can(a,b)) spfa(i,j,a,b,k);
}
}
for(int i = 1;i <= g;i ++)
{
memset(vis,0x3f,sizeof(vis));ans = 1e6;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,0);
if(ans == 1e6) puts("-1");
else printf("%d\n",ans);
}
}1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 然后我们会发现将数组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[] = {0,1,0,-1};
const int Y[] = {1,0,-1,0};
int n,m,g,ma[35][35],dis[35][35][35][35][5],used[35][35],ans,a,b,c,d,ex,ey,vis[35][35][5];
struct zt
{
int x,y;
};
queue<zt>q;
bool can(int x,int y)
{
if(x < 1||x > n) return false;
if(y < 1||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,0,sizeof(used));
q.push((zt){x,y});
dis[x][y][x][y][ji] = 0;
while(!q.empty())
{
zt u = q.front();q.pop();
used[u.x][u.y] = 0;
for(int i = 0;i < 4;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] + 1)
{
dis[x][y][x1][y1][ji] = dis[x][y][u.x][u.y][ji] + 1;
if(!used[x1][y1])
{
q.push((zt){x1,y1});
used[x1][y1] = 1;
}
}
}
}
}
}
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[4] = {0,0,0,0},ji,lu;
for(int i = 0;i < 4;i ++)
{
lu = 1e6;
for(int j = 0;j < 4;j ++)
{
int x = sx + X[j],y = sy + Y[j];
if(can(x,y)&&lu > dis[x][y][kx][ky][(j+2)%4]&&!used2[j])
lu = dis[x][y][kx][ky][(j+2)%4],ji = j;
}
if(lu != 1e6)
{
int x = sx + X[ji],y = sy + Y[ji];used2[ji] = 1;
dfs(sx,sy,x,y,cnt+dis[x][y][kx][ky][(ji+2)%4]+1,(ji+2)%4);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&g);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
scanf("%d",&ma[i][j]);
memset(dis,0x3f,sizeof(dis));
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
if(!ma[i][j]) continue;
for(int k = 0;k < 4;k ++)
{
a = i + X[k],b = j + Y[k];
if(can(a,b)) spfa(i,j,a,b,k);
}
}
for(int i = 1;i <= g;i ++)
{
memset(vis,0x3f,sizeof(vis));ans = 1e6;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&ex,&ey);
dfs(a,b,c,d,0,4);
if(ans == 1e6) puts("-1");
else printf("%d\n",ans);
}
}