描述
小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
在一个 n*m 棋盘上有 n*m 个格子，其中有且只有一个格子是空白的，其余 n*m-1个格子上每个格子上有一个棋子，每个棋子的大小都是 1*1 的；
有些棋子是固定的，有些棋子则是可以移动的；
任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘，游戏可以玩 q 次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候，空白的格子在第 EXiEXi行第 EYiEYi 列，指定的可移动棋子的初始位置为第 SXiSXi 行第 SYiSYi 列，目标位置为第 TXiTXi 行第 TYiTYi 列。
假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。
格式
输入格式
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n、m 和 q；
接下来的 n 行描述一个 n*m 的棋盘，每行有 m 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。
接下来的 q 行，每行包含 6 个整数依次是 EXiEXi、EYiEYi、SXiSXi、SYiSYi、TXiTXi、TYiTYi，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。
输出格式
输出有 q 行，每行包含 1 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出−1。
限制
每个测试点1s。
提示
样例说明
棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。
-
第一次游戏，空白格子的初始位置是 (3, 2)（图中空白所示），游戏的目标是将初始位置在(1, 2)上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置(2, 2)（图中红色的格子）上。
移动过程如下:
-
第二次游戏，空白格子的初始位置是（1, 2）（图中空白所示），游戏的目标是将初始位置在（2, 2）上的棋子（图中绿色圆圈所示）移动到目标位置 (3, 2)上。
要将指定块移入目标位置，必须先将空白块移入目标位置，空白块要移动到目标位置，必然是从位置（2，2）上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位置，游戏无法完成。
数据范围
对于 30%的数据，1 ≤ n, m ≤ 10，q = 1；
对于 60%的数据，1 ≤ n, m ≤ 30，q ≤ 10；
对于 100%的数据，1 ≤ n, m ≤ 30，q ≤ 500。
解题报告
看到这道题，又有一点小兴奋，因为是华容道这个游戏（好吧，好像是游戏我都很激动-.-），但是由于对BFS的不熟悉，（也就是“公式”还没有背到），知道要写BFS的我也无能为力。。。。所以顺带复习了一下BFS和增量数组。
增量数组：zl[2][4]={{0,0,1,-1},{1,-1,0,0}};
bfs:
int bfs()
{
//初始化，初始状态存入队列 //或queue<int>q;
//队首指针 head=0；尾指针 tail=1； // q.push(1)
do //while (!q.empty())
{
//指针head++； 指向待扩展结点 //int now=q.front(),q.pop()
for (int i=;i<=max;i++)
{
if (/*子节点符合条件*/)
{
tail ++;//新节点存入队尾 //q.push(i)
if(/*新节点与原结点重复*/)
//删去该节点(取消入队，tail--)
else
if(/*新节点是目标结点*/) //输出并退出 }
}
} while (head<tail);
}
啊，最后这道题还是只写了一个70分的代码，弃坑。（不不不，以后有时间还是要写的）
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int n,m,q;
int chess[][];
const int zl[][]={{,,-,},{,,,-}};
bool b[][][][];
struct pp{
int ex,ey,sx,sy;
int step;
};
pp node[];
bool pd(int x1,int y1,int x2,int y2)
{
if (x2<||x2>n||y2<||y2>m||!chess[x2][y2]) return false;
if (b[x1][y1][x2][y2]) return false;
b[x1][y1][x2][y2]=true;
return true;
}
void bfs()
{
memset(b,false,sizeof(b));
int tx,ty;
scanf("%d%d%d%d%d%d",&node[].ex,&node[].ey,&node[].sx,&node[].sy,&tx,&ty);
int head=,tail=;
if (tx==node[].sx&&ty==node[].sy) {cout<<<<endl;return ;}
b[node[].sx][node[].sy][node[].ex][node[].ey]=true;
node[tail].step=;//初始化
while(head<=tail)
{
for (int i=;i<=;i++)
{
int x=node[head].sx,y=node[head].sy;
int x1=node[head].ex+zl[][i],y1=node[head].ey+zl[][i];
if (x==x1&&y==y1) {x=node[head].ex;y=node[head].ey;}/*!!!!*/
if (pd(x,y,x1,y1))
{
tail++;
node[tail].sx=x;node[tail].sy=y;//入队
node[tail].ex=x1;node[tail].ey=y1;
node[tail].step=node[head].step+;
if (x==tx&&y==ty) {cout<<node[tail].step<<endl;return ;}
}
}
head++;
}while (head<tail);
cout<<-<<endl;
return ;
}
int main()
{
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
cin>>n>>m>>q;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&chess[i][j]);
for (int i=;i<=q;i++)
bfs();
return ;
}
完整100代码是spfa 和 bfs：（复制版本）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define MaxN 35
using namespace std;
const int
INF=~0U>>,
dx[]={,,-,},
dy[]={-,,,};//注意顺序，才易实现0变1，1变0；2变3，3变2
int mat[MaxN][MaxN],dis[MaxN][MaxN][];
bool vis[MaxN][MaxN][];
int step[MaxN][MaxN][][];
int d[MaxN][MaxN];
int n,m,q,test,ex,ey,sx,sy,tx,ty;
struct node
{
int x,y;
};
struct node2
{
int x,y,k;
};
bool inside(int x, int y)
{
return (x>=&&x<=n&&y>=&&y<=m);
}
int spfa()
{
queue<node2> q;
memset(vis,false,sizeof(vis));
while(!q.empty()) q.pop();//局部队列，可能非空，所以清空
for(int k=;k<;k++)//把初始位置棋子与空格相邻，四个方向组成的四种可能的步数入队，当成四个源点。
if(dis[sx][sy][k]!=INF)
{
q.push((node2){sx,sy,k});
vis[sx][sy][k]=true;
}
while(!q.empty())
{
int x=q.front().x;
int y=q.front().y;
int k=q.front().k;
q.pop();
vis[x][y][k]=false;
for(int i=;i<;i++)
{
int _x=x+dx[i];//棋子(x,y)扩展的点(_x,_y)
int _y=y+dy[i];
if(inside(_x,_y))
if(mat[_x][_y])
if(step[x][y][k][i]!=INF)//棋子(x,y)k方向空格可以移到棋子(x,y)i方向。
if(dis[_x][_y][i^]>dis[x][y][k]+step[x][y][k][i]+)
{//棋子(x,y)k方向空格移到棋子(x,y)i方向,再把棋子移到空格上，所以+1，空格变成i^1方向。
dis[_x][_y][i^]=dis[x][y][k]+step[x][y][k][i]+;
if (not vis[_x][_y][i^])
{
q.push((node2){_x,_y,i ^ });
vis[_x][_y][i^]=true;
}
}
}
}
int ans=INF;
for(int i=;i<;i++)
if(dis[tx][ty][i]<ans)
ans=dis[tx][ty][i];//找出目标位置与空格相邻四种情况最少步数
return (ans==INF)? -:ans;
}
int bfs(int sx,int sy,int tx,int ty)//将空格从(sx,sy)移到(tx,ty)的步数
{
if(!mat[sx][sy])
return INF;
if(!mat[tx][ty])
return INF;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
d[i][j]=INF;//INF可以做为没有到过的标志
d[sx][sy]=;
queue<node> q;//局部队列，可能非空，所以清空
while(!q.empty()) q.pop();
q.push((node){sx,sy});
while(!q.empty())
{
if(d[tx][ty]!=INF)
return d[tx][ty];
int x=q.front().x;
int y=q.front().y;
q.pop();
for(int i=;i<;i++)
{
int _x=x+dx[i];
int _y=y+dy[i];
if(inside(_x,_y))
if(mat[_x][_y]&&d[_x][_y]==INF)
{
d[_x][_y]=d[x][y]+;
//if(d[tx][ty]!=INF)
// return d[tx][ty];
//与下面不等价，有可能(sx,sy)与（tx,ty)一样,所以最好放在出队前判断
//if (_x==tx&&_y==ty) return d[tx][ty];????
q.push((node){_x,_y});
}
}
}
return INF;
}
void init()
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int v=mat[i][j];
mat[i][j]=;//此位置可能是0或1,均改成0，因为移动空格不能移动棋子(i,j)
for (int k=;k<;k++)
for (int l=;l<;l++)
step[i][j][k][l]=bfs(i+dx[k],j+dy[k],i+dx[l],j+dy[l]);
//step[i][j][k][l] 棋子(i,j)k方向相邻的空格移动到相邻的l方向的步数，
mat[i][j]=v;//还原
}
}
int getAns()
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(sx==tx&&sy==ty)//初始位置与目标位置同，0步
return ;
if(sx==ex&&sy==ey)//初始位置与空格位置同，无解
return -;
if(!inside(ex,ey)||!inside(sx,sy)||!inside(tx,ty))//三个位置至少有一个在棋盘外
return -;
if(!mat[ex][ey]||!mat[sx][sy]||!mat[tx][ty])////三个位置至少有一个是固定的
return -;
for(int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k<;k++)
dis[i][j][k]=INF;
mat[sx][sy]=;//此时一定是1,改成0，因为前面已经判断过
for(int k=;k<;k++)
dis[sx][sy][k]=bfs(ex,ey,sx+dx[k],sy+dy[k]);
//dis[sx][sy][k]表示将空格移到(sx,sy)相邻并在k方向上的步骤
mat[sx][sy]=; //还原
return spfa();
}
int main()
{
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
scanf("%d%d%d",&n,&m,&test);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&mat[i][j]);
init();
while(test--)
printf("%d\n",getAns());
return ;
}
啊，太长了，一定要好好消化。。。