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