C++貪心算法實現(xiàn)馬踏棋盤

更新時間：2022年02月15日 11:06:15 作者：瘋狂的布布

這篇文章主要為大家詳細介紹了C++貪心算法實現(xiàn)馬踏棋盤，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C++貪心算法實現(xiàn)馬踏棋盤的具體代碼，供大家參考，具體內(nèi)容如下

算法實現(xiàn)流程：

步驟1：初始化馬的位置（結構體horse {x, y}）

步驟2：確定馬從當前點出發(fā)，可跳躍的附近8個點，以結構體Jump數(shù)組給出，但需判斷當前給出的附近8個點是否曾經(jīng)訪問過，或者是否這8個點超出棋盤尺寸。

步驟3：跟據(jù)步驟2確定跳躍的點，分別計算可跳躍點的下下一步，可跳躍點的個數(shù)。并選出下下步可跳躍點數(shù)最少的點作為馬下一步跳躍的點。（舉例說明：馬當前所在點坐標（4，4），下一步可跳躍點有（5，2），（6，3），且（5，2）下一步可跳躍點有3個，（6，3）下一步可跳躍點2個；3 > 2這個時候，選擇下下一跳小的點進行跳躍，則馬下一跳為（6，3））

流程圖：

#pragma once
#include <iostream>
#include <math.h>
using namespace std;
#define SAFE_DELETE(x) if (x != NULL) {delete(x); x = NULL;}
#define SAFE_DELETE_ARR(x) if (x != NULL) {delete[](x); x = NULL;}
#define PRING_ARR(title, arr, n) {cout << title << " "; for (int i=0; i<n; i++) {cout << arr[i] << " ";} cout << endl;}
?
#define INF 9999999
?
typedef struct
{
?? ?int x;
?? ?int y;
}Location;
?
typedef struct
{
?? ?int delx;
?? ?int dely;
}Jump;
?
class HorseRun
{
private:
?? ?int** altas;
?? ?int N; //棋盤的寬
?? ?Location horse; //馬當前的位置
public:
?? ?HorseRun()
?? ?{
?? ??? ?N = 8;
?? ??? ?altas = new int* [N]();
?? ??? ?for (int j = 0; j < N; j++)
?? ??? ?{
?? ??? ??? ?altas[j] = new int[N]();
?? ??? ??? ?memset(altas[j], 0, sizeof(int) * N);
?? ??? ?}
?
?? ??? ?//隨機生成馬的初始位置
?? ??? ?horse = { rand() % N, rand() % N };
?? ??? ?altas[horse.x][horse.y] = 1;
?? ??? ?cout << "馬初始位置:" << "(" << horse.x << "," << horse.y << ")" << endl;
?
?? ??? ?Visit();
?? ?}
?
?? ?~HorseRun()
?? ?{
?? ??? ?for (int i = 0; i < N; i++)
?? ??? ??? ?SAFE_DELETE_ARR(altas[i]);
?? ??? ?SAFE_DELETE_ARR(altas);
?? ?}
?
?? ?inline void Visit()
?? ?{
?? ??? ?Jump jump[8] = { {1,-2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2} };
?
?? ??? ?int max_visit = 63;
?? ??? ?int forward_x, forward_y, forward_xx, forward_yy, w_cnt, min_cnt, tmp_run_x, tmp_run_y;
?? ??? ?while (max_visit-- > 0)
?? ??? ?{
?? ??? ??? ?min_cnt = INF;
?? ??? ??? ?//棋子可跳八個方位
?? ??? ??? ?for (int i = 0; i < 8; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?forward_x = horse.x + jump[i].delx;
?? ??? ??? ??? ?forward_y = horse.y + jump[i].dely;
?
?? ??? ??? ??? ?//判斷這兩個坐標是否有效
?? ??? ??? ??? ?if (forward_x < 0 || forward_x >= N || forward_y < 0 || forward_y >= N || altas[forward_x][forward_y] == 1)
?? ??? ??? ??? ??? ?continue;
?
?? ??? ??? ??? ?w_cnt = 0;
?? ??? ??? ??? ?for (int j = 0; j < 8; j++)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?forward_xx = forward_x + jump[j].delx;
?? ??? ??? ??? ??? ?forward_yy = forward_y + jump[j].dely;
?
?? ??? ??? ??? ??? ?if (forward_xx < 0 || forward_xx >= N || forward_yy < 0 || forward_yy >= N || altas[forward_xx][forward_yy] == 1)
?? ??? ??? ??? ??? ??? ?continue;
?? ??? ??? ??? ??? ?w_cnt++;
?? ??? ??? ??? ?}
?
?? ??? ??? ??? ?if (min_cnt > w_cnt)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?min_cnt = w_cnt;
?? ??? ??? ??? ??? ?tmp_run_x = forward_x;
?? ??? ??? ??? ??? ?tmp_run_y = forward_y;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?
?? ??? ??? ?//棋子移動判斷
?? ??? ??? ?if (min_cnt == INF)
?? ??? ??? ?{
?? ??? ??? ??? ?cout << "沒有找到可以移動的地方" << endl;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?horse.x = tmp_run_x;
?? ??? ??? ??? ?horse.y = tmp_run_y;
?? ??? ??? ??? ?altas[tmp_run_x][tmp_run_y] = 1;
?? ??? ??? ??? ?cout <<"第"<< 63 - max_visit << "步," << "棋子當前移動到:" << "(" << tmp_run_x << ", " << tmp_run_y << ")" << endl;
?? ??? ??? ?}
?? ??? ?}
?? ?}
};
?
#define ?_CRT_SECURE_NO_WARNINGS true
#include "HorseRun.h"
int main()
{
?? ?HorseRun app;
?? ?return 0;
}

運行結果輸出1-63步馬行駛的具體路徑信息：