C++[NOIP2013 提高组] 华容道

Question

求解！
[NOIP2013 提高组] 华容道
题目是这样的：
小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。

小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：

1. 在一个 n×m 棋盘上有n×m个格子，其中有且只有一个格子是空白的，其余n×m−1个格子上每个格子上有一个棋子，每个棋子的大小都是 1×1 的；

2. 有些棋子是固定的，有些棋子则是可以移动的；

3. 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。

游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。

输入描述
第一行有 3个整数，每两个整数之间用一个空格隔开，依次表示n,m,q；

接下来的 n 行描述一个n×m 的棋盘，每行有m个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。

每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。

输出描述
共q 行，每行包含 1 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出−1。
//写了3小时的代码，出了个SE！（系统错误）

Answer 1

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/727601
• 除此之外, 这篇博客: 练习 3-1 在上面有关折半查找的例子中，while循环语句内共执行了两次测试，其实只要一次就足够（代价是将更多的测试在循环外执行）。重写该函数，使得在循环内部只执行一次测试。中的 练习 3-1 在上面有关折半查找的例子中，while循环语句内共执行了两次测试，其实只要一次就足够（代价是将更多的测试在循环外执行）。重写该函数，使得在循环内部只执行一次测试。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 代码块

  #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;
  }
  

  如果程序设计有错误或更简洁的方法，欢迎并感谢您指正出示，谢谢！

• 以下回答由chatgpt基于相关博客总结生成:

  问题解答：

  华容道游戏可以看作是一个搜索问题，可以使用广度优先搜索算法来解决。算法的流程如下：

  1. 定义每个游戏状态：对于华容道游戏的每个状态，可以用一个n*m的二维数组表示。

  2. 定义状态转移函数：对于可行的移动，建立一个函数，可以将当前状态转移到下一个状态。

  3. 使用广度优先搜索算法搜索能够到达目标状态的状态序列，找到其中最短的那个。

  4. 最后需要判断能否到达目标状态，如果不能，返回-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方法用于交换棋盘上两个位置的棋子。