走迷宫(回溯)(c++)

走迷宫(回溯)(c++),第1张

#include        //第一次写走迷宫的算法,还请路过的给位大佬指教;
#include 
#include 
int ar[10][12] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 定义迷宫
                      1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
                      1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
                      1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
                      1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
                      1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
                      1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
                      1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
                      1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
                      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

using namespace std;
class migong
{
private:
    int init_x;
    int init_y;
    int end_x;
    int end_y;
    vector > path;
    /* data */
public:
    migong(int x , int y , int a, int b) : init_x(x) , init_y(y) , end_x(a) , end_y(b){}
    void answer();
    bool prime(int x, int y, int end_x, int end_y, int pre_x, int pre_y);
};
void migong::answer()
{
    int pre_x = -1, pre_y = -1;
    if(ar[init_x][init_y] == 1 || ar[end_x][end_y] == 1){
        cout<< "初始位置或终点信息有误" << endl;
        return;
    }
    prime(init_x, init_y, end_x, end_y, pre_x, pre_y);
    return;
}

bool migong::prime(int x, int y, int end_x, int end_y, int pre_x, int pre_y)
{
    if (x == end_x && y == end_y)
    {
        // path.push_back(make_pair(x , y));
        for (int i = 0; i < path.size(); ++i)
        {
            cout << path[i].first << " " << path[i].second << endl;
            ;
        }
        cout << endl;
        path.clear();
        return true;
    }

    if (x + 1 != pre_x && ar[x + 1][y] == 0)
    {
        path.push_back(make_pair(x + 1, y));
        if (prime(x + 1, y, end_x, end_y, x, y))
        {
            return true;
        }
        else
        {
            ar[x + 1][y] = 1;
            path.pop_back();
        }
    }
    if (x - 1 != pre_x && ar[x - 1][y] == 0)
    {
        path.push_back(make_pair(x - 1, y));
        if (prime(x - 1, y, end_x, end_y, x, y))
        {
            return true;
        }
        path.pop_back();
        ar[x - 1][y] = 1;
    }
    if (y - 1 != pre_y && ar[x][y - 1] == 0)
    {
        path.push_back(make_pair(x, y - 1));
        if (prime(x, y - 1, end_x, end_y, x, y))
        {
            return true;
        }
        path.pop_back();
        ar[x][y - 1] = 1;
    }
    if (y + 1 != pre_y && ar[x][y + 1] == 0)
    {
        path.push_back(make_pair(x, y + 1));
        if (prime(x, y + 1, end_x, end_y, x, y))
        {
            return true;
        }
        path.pop_back();
        ar[x][y + 1] = 1;
    }
    return false;
}

int main()
{
    migong test(1,1,8,10);//前两个是初始位置,后两个是终点位置
    test.answer();
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/3002927.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表(0条)

保存