C++贪心算法实现马踏棋盘问题

C++马踏棋盘的贪心算法

转载请注明:
http://blog.csdn.net/l773575310/article/details/53727286

第一次看马踏棋问题时没有想到用贪心算法,结果穷举起来光5*5的棋盘也运行了很久才出来一条路径。然后看了不少关于马踏棋的解法,大体也看懂了,简单的的说,就是让棋子每次走的下一个位置的出口尽可能少

贪心算法在这里体现:
尽可能走出口少的路,因为如果走出口多的路,后面出口少的路越多,越容易走到死路,即没有路可走。

看下图:
假设小马哥在图中的位置,且其他位置都还没有走过,他有6个红色位置可以走
《C++贪心算法实现马踏棋盘问题》

如果他走右下角,那他只有一个出口(绿色的)
《C++贪心算法实现马踏棋盘问题》

如果走左下角那个,那他有3个出口
《C++贪心算法实现马踏棋盘问题》

以此类推:走偏左下角,5个
《C++贪心算法实现马踏棋盘问题》

最后看一下小马哥下一个位置的出口数量:
《C++贪心算法实现马踏棋盘问题》

如果为0说明走到死路,有可能是走完了所有格子,也有可能没有走完,那就需要往回走了(类似弹栈)。

下面就是代码了

首先是一些初始化

//宏定义,宽、高、一共的格子数
#define WIDTH 8
#define HEIGHT 8
#define PLACE_COUNT ((WIDTH)*(HEIGHT)) 

//放置棋子的位置
typedef struct position {
    int x;
    int y;
}Position;

//马棋可以走的8个方向(相对当前位置)
vector<Position> DIR({ { -1,-2 },{ 1,-2 },{ 2,-1 },{ 2,1 },{ 1,2 },{ -1,2 },{ -2,1 },{ -2,-1 } });

//这个用来排序下一个位置用到,具体看下面的函数
typedef pair<int, int> PAIR;

然后在 main函数中

int main()
{
    //棋盘所有格子初始化都没走过,为false
    vector<bool> place(PLACE_COUNT, false);
    //顺序存放棋子所经过的所有位置
    vector<Position> pos;

    //这里假设从(0,2)开始,这个函数下面讲
    if (emplaceHorse(0, 2, 0, place, pos))
        for (int i = 0; i < PLACE_COUNT; i++)
            cout << i + 1 << ":(" << pos[i].x + 1 << "," << pos[i].y + 1 << ") ";
    else
        cout << "what the fuck!?";

    return 0;
}

这里解释一下两个vector:

pos,按顺序存了小马哥走过的位置,其实充当栈来用。

place ,存了棋盘的每一个位置,第一行第一列就是place[0],第二行第一列就是place[8],最后一行最后一列就是place[63],他的值类型bool,true代表这个位置已经走过,false代表没走过。
《C++贪心算法实现马踏棋盘问题》

接下来就是递归了
参数:小马哥的x,y坐标,走的第几步count,还有上面说的两个vector

bool emplaceHorse(int x, int y, int count, vector<bool> & place, vector<Position> & pos)
{
    //判断当前x,y是否在棋盘内,若在,是否此位置已经走过,因为||操作符有短路作用,所以不用怕后面place越界。
    if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT || place[x + y*WIDTH])
        return false;

    count++;
    place[x + y*WIDTH] = true;          //标志此位置已走过
    pos.push_back({ x,y });             //将此位置压入已走路径pos

    //判断是否已经走满格子的数量
    if (count == PLACE_COUNT)
        return true;

    vector<PAIR> vecMap = findPosition(x, y, place);
    //遍历这个已经出口数量从小到大排好序的位置
    for (int i = 0; i < vecMap.size(); i++)
        //将当前选中的位置作为下一个位置,继续递归
        if (emplaceHorse(vecMap[i].first % WIDTH, vecMap[i].first / WIDTH, count, place, pos))
            return true;

    //当前路径不适合,标志未走过,弹出路径队列pos
    place[x + y*WIDTH] = false;
    pos.pop_back();
    return false;
}

vecMap[i].first % WIDTH 就是位置的x,
vecMap[i].first / WIDTH 就是位置的y.

下面就是贪心的核心了,找出口少的路径

vector<PAIR> findPosition(int x, int y, vector<bool> & currentPos)
{
    //key为位置,value为此位置的出口数量
    map<int, int> p;
    //第一层循环,当前位置可选的下一个位置,就是上面那些图片的红色的位置
    for (int i = 0; i < DIR.size(); i++)
    {
        int temX = DIR[i].x + x;
        int temY = DIR[i].y + y;
        if (temX < 0 || temX >= WIDTH || temY < 0 || temY >= HEIGHT || currentPos[temX + temY * WIDTH])
            continue;
        int count = 0;
        //第二层循环,计算可选的下一个位置的出口数量,上面那些图片绿色的位置
        for (int j = 0; j < DIR.size(); j++)
        {
            int outX = DIR[j].x + temX;
            int outY = DIR[j].y + temY;
            if (outX < 0 || outX >= WIDTH || outY < 0 || outY >= HEIGHT || currentPos[outX + outY * WIDTH])
                continue;
            count++;
        }
        //记录这个位置,还有他的出口数量
        p[temX + temY * WIDTH] = count;
    }

    //将所有可选位置的出口数量从小到大排序,即按value排序
    vector<PAIR> vecP(p.begin(), p.end());
    sort(vecP.begin(), vecP.end(), [](const PAIR& p1, const PAIR& p2) { return p1.second < p2.second; });

    //返回排好序的vector
    return vecP;
}

运行结果如下:
8*8的棋盘,从(0,2)开始走一条不重复的路,遍历完整个棋盘。
《C++贪心算法实现马踏棋盘问题》

自己画了一下图,可以发现小马哥基本上沿着边走的,因为边路出口少。
《C++贪心算法实现马踏棋盘问题》

源码下载:
C++贪心算法实现马踏棋盘问题(.cpp文件)

    原文作者:贪心算法
    原文地址: https://blog.csdn.net/l773575310/article/details/53727286
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞