中国象棋中的跳马问题

题目描述
现在棋盘的大小不一定，由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;
}

#include<stdio.h>
 #include<string.h>
 #include<queue>
 #include<iostream>
using namespace std;
const int N=105;
int p,q,sx,sy,tx,ty;
int k,vis[N][N],a[N][N];
int dx[8]= {2,2,-1,1,-2,-2,-1,1},dy[8]= {-1,1,-2,-2,-1,1,2,2};
int yd[4][2]= {1,0,0,-1,-1,0,0,1};
struct Node
{
    int x,y,cnt;
}que[15005];///注意队列的大小
int bfs()
{
    Node tou,next;
    tou.x=sx;
    tou.y=sy;
    tou.cnt=0;
    int front=1,rear=1;
    que[front]=tou;
    while(front&lt;=rear)
    {
        tou=que[front];//取队头
        front++;//删除队头
        if(tou.x==tx&amp;&amp;tou.y==ty)//到达目标位置
            return tou.cnt;
        int nx,ny;
        for(int i=0; i&lt;8; i++)
        {
            int t=i/2,x,y;
            x=tou.x,y=tou.y;
            int m=x+yd[t][0],n=y+yd[t][1];
            if(m&gt;0&amp;&amp;m&lt;=p&amp;&amp;n&gt;0&amp;&amp;n&lt;=q&amp;&amp;vis[m][n]) continue;///判断撇腿，这里若换成四个循环判断会节省时间
            nx=tou.x+dx[i];
            ny=tou.y+dy[i];
            if(nx&gt;=1&amp;&amp;nx&lt;=p&amp;&amp;ny&gt;=1&amp;&amp;ny&lt;=q&amp;&amp;vis[nx][ny]==0&amp;&amp;a[nx][ny]==0)
            {
                next.x=nx;
                next.y=ny;
                next.cnt=tou.cnt+1;
                ++rear;
                que[rear]=next;//加入队尾
                a[nx][ny]=1;
            }
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf("%d",&amp;t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        scanf("%d%d",&amp;p,&amp;q);
        scanf("%d%d%d%d",&amp;sx,&amp;sy,&amp;tx,&amp;ty);
        scanf("%d",&amp;k);
        int i,x,y;
        for(i=0; i&lt;k; i++)
        {
            scanf("%d%d",&amp;x,&amp;y);
            vis[x][y]=1;//标记有障碍的位置
        }
        int ans=bfs();
        if(ans&gt;=0)
            printf("%d\n",ans);
        else
            printf("can not reach!\n");
    }
    return 0;
}

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: 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()

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

中国象棋中的跳马问题

算法思想