欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

NOJ1043——算法实验三——跳马

程序员文章站 2022-06-25 16:08:09
跳马描述:在国际象棋中,马的走法与中国象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。输入:本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),表示测例的个数,接下来的每一行有四个以空格分隔的整数,分别表示马当前位置及目标位置的横、纵坐标C(x,y)和G(x...

跳马

NOJ1043——算法实验三——跳马
描述

在国际象棋中,马的走法与中国象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。

现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。

输入

本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),表示测例的个数,接下来的每一行有四个以空格分隔的整数,分别表示马当前位置及目标位置的横、纵坐标C(x,y)和G(x,y)。坐标由1开始。

输出

对于每个测例,在单独的一行内输出一个整数,即马从当前位置跳到目标位置最少的跳数。

输入样例:

2
1 1 2 1
1 5 5 1

输出样例:

3
4

源代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int walk[8][2] =
{
    1, 2,
    2, 1,
    -1,-2,
    -2,-1,
    -1, 2,
    1,-2,
    -2,1,
    2,-1
};
int maze[200][200];
int step[200 * 200];
int make_new_place(int row,int col,int type)
{
    row += walk[type][0];
    col += walk[type][1];
    if(row < 0|| row >= 200 || col < 0 || col >= 200)
    {
        return -1;
    }
    if(maze[row][col] != 0)
    {
        return -1;
    }
    else
    {
        return row * 200 + col;
    }
}
void bfs(queue<int> q,int end_r,int end_c)
{
    int i;
    while(!q.empty())
    {
        int pop_num = q.front();
        q.pop();
        int place_r = pop_num / 200;
        int place_c = pop_num % 200;
        int new_num[8];
        for (i = 0; i < 8; i++)
        {
            new_num[i] = make_new_place(place_r, place_c, i);
            if(new_num[i] != -1)
            {
                step[new_num[i]] = step[pop_num] + 1;
                int row = new_num[i] / 200;
                int col = new_num[i] % 200;
                maze[row][col] = pop_num;
                q.push(new_num[i]);
                if(row == end_r && col == end_c)
                {
                    return;
                }
            }
        }
    }
}
int main()
{
    queue<int> q;
    int begin_x, begin_y;
    int end_x, end_y;
    int n, i, j, k;
    cin >> n;
    int ans[100];
    for (i = 0; i < n; i++)
    {
        cin >> begin_x >> begin_y;
        cin >> end_x >> end_y;
        q.push((begin_x - 1) * 200 + (begin_y - 1));
        maze[begin_x - 1][begin_y - 1] = 1;
        bfs(q, end_x - 1, end_y - 1);
        ans[i] = step[(end_x - 1) * 12 + (end_y - 1)];
        q = queue<int>();
        ans[i] = step[(end_x - 1) * 200 + (end_y - 1)];
        for (j = 0; j < 200; j++)
        {
            for (k = 0; k < 200; k++)
            {
                maze[j][k] = 0;
                step[j * 200 + k] = 0;
            }
        }
    }
    for (i = 0; i < n; i++)
    {
        cout << ans[i] << endl;
    }
}

这道题目和之前的电子老鼠闯迷宫类似,只是扩展结点变成八个方向的“日”型。
具体可以参见之前的博客。

本文地址:https://blog.csdn.net/qq_45757722/article/details/109272297

相关标签: 算法设计与分析