UC知道一个有挑战性的算法题
来源：百度知道 编辑：UC知道 时间：2024/06/06 02:58:16
中国象棋的棋盘可以用一个10行9列的二维数组来表示。如果马（棋子的名称）当前所在位置是(x,y)，它跳一步可能到达的位置最多有8个，如下图所示。
要求设计一个算法，对于任意给定的棋盘上的坐标位置pc和整数k，输出马从位置pc开始连跳k步可以到达的坐标位置。
输入数据从文本文件“data.txt”中读取。该文件有两行：第1行有两个整数，表示起始位置pc的行坐标值和列坐标值；第2行只有一个整数，表示k值。
输出结果显示在屏幕上，每行显示一个坐标，逐行逐列显示。
高手最好是用C++描述一下算法
嫌麻烦的可以说一下思路 写的或是说的全面的加分，最少200
要求设计一个算法，对于任意给定的棋盘上的坐标位置pc和整数k，输出马从位置pc开始连跳k步可以到达的坐标位置。
输入数据从文本文件“data.txt”中读取。该文件有两行：第1行有两个整数，表示起始位置pc的行坐标值和列坐标值；第2行只有一个整数，表示k值。
输出结果显示在屏幕上，每行显示一个坐标，逐行逐列显示。
高手最好是用C++描述一下算法
嫌麻烦的可以说一下思路 写的或是说的全面的加分，最少200
这没有啥难度的吧，直接递归就可以了啊
算法描叙：
1. 从给定位置x,y出发，对候选的八个位置
(x-2,y+1)
(x+2,y+1)
(x-2,y-1)
(x+2,y-1)
(x-1,y+2);
(x+1,y+2)
(x-1,y-2)
(x+1,y-2)
确定是否越界，如果没有越界，就分别对其进行递归。
2.当递归次数到达k次，也就说马走了k次，把最终坐标保存。
当所有递归结束，将获得所谓的位置。
#pragma warning(disable:4786)
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
bool isValidPos(int i, int j)
{
if(i<0 || i>=10) return false;
if(j<0 || j>=9) return false;
return true;
}
void getPos(int x, int y, int j, int k, set<pair<int, int> > &vpair)
{
if(j == k)
{
vpair.insert(pair<int, int>(x, y));
return ;
}
if(isValidPos(x-2,y+1)) getPos(x-2, y+1, j+1, k, vpair);
if(isValidPos(x+2,y+1)) getPos(x+2, y+1, j+1, k, vpair);
if(isValidPos(x-2,y-1)) getPos(x-2, y-1, j+1, k, vpair);
if(isValidPos(x