中国象棋中的跳马问题

Question

题目描述
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
输入
第一行输入n表示有n组测试数据。
每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。
输出
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
样例输入
2
9 10
1 1 2 3
0
9 10
1 1 2 3
8
1 2
2 2
3 3
3 4
1 4
3 2
2 4
1 3
样例输出
1
can not reach!
我的思路是：一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个二维数组，将除阻挡点赋值为-1外，其它点都初始化为0，用来记录此点是第几步到达的，然后再入队，如果加入过队列当中，就不需要再加入了，马成功到达终点，或者搜索到了终点，搜索即停止，然后输出相应答案即可。但我不知道为什么答案错误，求解答！
Expected | Yours
25 24

#include <iostream>
#include <iomanip>
#include <cstdio>
#define MVNum 105
using namespace std;

int dx[8] = {-2,-2, -1, 1, 2, 2, 1, -1};
int dy[8] = {-1,1, -2, -2, 1, -1, 2, 2};
int m[2]= {1,-1};
typedef struct
{
    int length,width;
    int sx, sy, ex, ey,h;
    int arcs[MVNum][MVNum];
} Graph;

bool visited[MVNum][MVNum];
bool right1(Graph &g,int nx, int ny)
{
    return nx>=0&&nx<=g.length &&ny>= 0 && ny <=g.width && !visited[nx][ny];
}
bool right2(Graph &g,int x,int y,int i)
{
    int nx,ny;
    if(i<2)
        nx=x+m[1];
    else if(i>=2&&i<4)
        ny=y+m[1];
    else if(i>=4&&i<6)
        nx=x+m[0];
    else
        ny=y+m[0];
    return g.arcs[nx][ny]!=-1;
}
void BFS(Graph &g)
{
    int Queue[MVNum * MVNum][2];
    int front = 1, rear = 1;
    Queue[rear][0]=g.sx;
    Queue[rear][1]=g.sy;
    rear++;
    while (front < rear&&rear<=MVNum*MVNum)
    {
        int x = Queue[front][0];
        int y = Queue[front][1];
        front++;
        if (x==g.ex&&y==g.ey)
        {
            cout<<g.arcs[x][y]<<endl;
            return ;
        }
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (right1(g,nx, ny)&&right2(g,x,y,i) &&g.arcs[nx][ny]==0)
            {
                g.arcs[nx][ny] = g.arcs[x][y] + 1;
                Queue[rear][0] = nx;
                Queue[rear][1] = ny;
                rear++;
            }
        }
    }
    cout<<"can not reach!"<<endl;
}
void destroy(Graph &g)
{
    g.length=g.width=0;
}
int main()
{
    Graph g;
    int n;
    cin>>n;
    while (n--)
    {
        cin>>g.length>>g.width;
        for (int i = 1; i <=g.length; i++)
        {
            for (int j = 1; j <=g.width; j++)
            {
                g.arcs[i][j]=0;
                visited[i][j] = false;
            }
        }
        cin>>g.sx>>g.sy>>g.ex>>g.ey;
        cin>>g.h;
        while (g.h--)
        {
            int x, y;
            cin>>x>>y;
            g.arcs[x][y]=-1;
            visited[x][y] = true;
        }
        BFS(g);
        destroy(g);
    }
    return 0;
}

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7713105
• 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 我们老师给我们花了100个星星的重要，那就是非常重要，快速排序。名字就很嚣张。。。言归正传，快排采用了分治算法。把大问题，分解成小问题。首先我们先找一个基准值，基准值的寻找法，有很多，这里我先用一个取边上值得方法，找到基准值以后呢拿着这个基准值和所有数组比较，使这个数组中比基准值小的都放左边，比基准值大的都放到右边，然后就把原来数组分成三块，中间基准值，左边都是比它小的，右边都是比它大的。然后这两个数组，继续分，一直分。直到他的终止条件，也就是小数组有序了就停止，那么什么时候有序停止呢？小区间长度为1或者长度为0的时候，就是有序了。所有小数组都有序了，那么就是整个数组有序了。只是原理，那么问题，又来了，怎么放左放右呢？我目前会三种。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 算法思想

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

  我可以为您提供以下代码思路，帮助您解决这个问题：

  # 首先定义一个变量来表示每个位置是第几步走到的
  # 先把它们全部初始化为0
  steps = [[0]*q for _ in range(p)]
  
  # 接下来定义一个队列，用来存储还需要走的点
  queue = []
  
  # 定义一个辅助函数，用来判断某个位置是否可以走
  def can_move(i, j, x, y):
      """
      i,j: 当前位置的坐标
      x,y: 目标位置的坐标
      """
      dx, dy = abs(i-x), abs(j-y)
      if dx > 2 or dy > 2 or dx+dy == 3:
          # 如果横向或纵向跨度过大，或者跨度小于3，都不能走
          return False
      if dx == 2 and dy == 0:
          # 如果是绊马腿的情况，不能走
          return False
      if steps[x][y] != 0:
          # 如果目标位置已经被标记过，也不能走
          return False
      return True
  
  # 然后定义一个函数用来处理一组测试数据
  def solve_one_case():
      # 首先读入数据
      p, q = map(int, input().split())
      startx, starty, endx, endy = map(int, input().split())
      m = int(input())
      for i in range(m):
          x, y = map(int, input().split())
          # 在障碍物上标记成-1
          steps[x][y] = -1
  
      # 把起点加入队列，并标记成第1步
      queue.append((startx, starty))
      steps[startx][starty] = 1
  
      # 开始搜索
      while queue:
          # 弹出队列
          x, y = queue.pop(0)
          # 判断是否到达终点
          if x == endx and y == endy:
              print(steps[x][y] - 1)
              # 如果到达了终点，就退出函数
              return
          # 开始分别判断马在当前位置向各个方向能否走
          if x-1 >= 0 and y-2 >= 0 and can_move(x, y, x-1, y-2):
              queue.append((x-1, y-2))
              steps[x-1][y-2] = steps[x][y] + 1
          if x-2 >= 0 and y-1 >= 0 and can_move(x, y, x-2, y-1):
              queue.append((x-2, y-1))
              steps[x-2][y-1] = steps[x][y] + 1
          if x+1 < p and y-2 >= 0 and can_move(x, y, x+1, y-2):
              queue.append((x+1, y-2))
              steps[x+1][y-2] = steps[x][y] + 1
          if x+2 < p and y-1 >= 0 and can_move(x, y, x+2, y-1):
              queue.append((x+2, y-1))
              steps[x+2][y-1] = steps[x][y] + 1
          if x-1 >= 0 and y+2 < q and can_move(x, y, x-1, y+2):
              queue.append((x-1, y+2))
              steps[x-1][y+2] = steps[x][y] + 1
          if x-2 >= 0 and y+1 < q and can_move(x, y, x-2, y+1):
              queue.append((x-2, y+1))
              steps[x-2][y+1] = steps[x][y] + 1
          if x+1 < p and y+2 < q and can_move(x, y, x+1, y+2):
              queue.append((x+1, y+2))
              steps[x+1][y+2] = steps[x][y] + 1
          if x+2 < p and y+1 < q and can_move(x, y, x+2, y+1):
              queue.append((x+2, y+1))
              steps[x+2][y+1] = steps[x][y] + 1
  
      # 如果到达了这里，说明不可能到达终点
      print("can not reach!")
  
  # 最后就是我们的主程序了
  n = int(input())
  for i in range(n):
      solve_one_case()
  

  以上是基本的思路和代码，当然还有一些细节和错误情况需要考虑，比如输入数据有误、无解等情况，您可以在实现时加以考虑。