求解！
[NOIP2013 提高组] 华容道
题目是这样的：
小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
在一个 n×m 棋盘上有n×m个格子，其中有且只有一个格子是空白的，其余n×m−1个格子上每个格子上有一个棋子，每个棋子的大小都是 1×1 的；
有些棋子是固定的，有些棋子则是可以移动的；
任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。
游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。
输入描述
第一行有 3个整数，每两个整数之间用一个空格隔开，依次表示n,m,q；
接下来的 n 行描述一个n×m 的棋盘，每行有m个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。
每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。
输出描述
共q 行，每行包含 1 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出−1。
//写了3小时的代码，出了个SE！（系统错误）
代码块
#include <stdio.h>
#include <stdlib.h>
int binsearch(int x, int v[], int n);
int main()
{
int x=3;
int v[]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n=10;
int a;
a=binsearch(x, v, n);
printf("%d\n", a);
system("pause");
return 0;
}
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low=0;
high=n-1;
mid=(low+high)/2;
while((low<=high)&&(x!=v[mid])){
(x<v[mid]) ? high=mid-1 : low=mid+1;
mid=(low+high)/2;
}
if (x==v[mid])
return mid;
else
return -1;
}
如果程序设计有错误或更简洁的方法，欢迎并感谢您指正出示，谢谢！
问题解答：
华容道游戏可以看作是一个搜索问题，可以使用广度优先搜索算法来解决。算法的流程如下：
定义每个游戏状态：对于华容道游戏的每个状态，可以用一个n*m的二维数组表示。
定义状态转移函数：对于可行的移动，建立一个函数，可以将当前状态转移到下一个状态。
使用广度优先搜索算法搜索能够到达目标状态的状态序列，找到其中最短的那个。
最后需要判断能否到达目标状态，如果不能，返回-1。
具体实现时，可以使用队列来存储状态序列，在队列中搜索目标状态序列，同时记录每个状态的步数，直到找到目标状态或者队列为空。
代码示例（Python）：
n, m, q = map(int, input().split()) # 输入棋盘行数，列数和游戏次数
for i in range(n):
board.append(list(map(int, input().split()))) # 输入棋盘状态
for i in range(q):
x, y, a, b = map(int, input().split()) # 输入空白格位置和目标位置
result = BFS(board, x, y, a, b) # 使用广度优先搜索算法
if result == -1:
print(-1)
else:
print(result)
def BFS(board, sx, sy, ex, ey):
q = [] # 队列
q.append((sx, sy, 0)) # 在队列中将起始状态加入
visited = set() # 已经访问过的状态
visited.add(str(board)) # 将当前状态加入已访问状态集合中
dx = [0, 0, -1, 1] # 上下左右四个方向
dy = [-1, 1, 0, 0]
while len(q) > 0:
x, y, step = q.pop(0) # 取出队首元素
if x == ex and y == ey: # 如果到达目标状态
return step # 返回最短步数
for d in range(4): # 四个方向尝试移动
nx, ny = x + dx[d], y + dy[d] # 移动后的位置
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue # 如果超出棋盘范围，忽略
if board[nx][ny] == 0:
continue # 如果是固定的格子，忽略
# 如果可以移动，则将当前状态加入队列中
swap(board, x, y, nx, ny)
if str(board) not in visited:
q.append((nx, ny, step + 1))
visited.add(str(board))
swap(board, x, y, nx, ny) # 复原棋盘状态
return -1 # 没有找到可行解
def swap(board, x1, y1, x2, y2):
temp = board[x1][y1]
board[x1][y1] = board[x2][y2]
board[x2][y2] = temp
其中，swap方法用于交换棋盘上两个位置的棋子。