C++貪婪演演算法實現馬踏棋盤

#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;
}