物理外挂-水排序谜题

待我称王封你为后i 2022-09-16 08:41 118阅读 0赞

#### 效果演示![在这里插入图片描述][8bd0e4ad6c144687bf74986450869f0d.gif_pic_center] ####

#### 代码 ####

#include <QCoreApplication>
    #include <QGuiApplication>
    #include <QPixmap>
    #include <QVector>
    #include <QImage>
    #include <QSet>
    #include <QQueue>
    #include <QPainter>
    #include <QMap>
    #include <QHash>
    #include <QThread>
    #include <QProcess>
    
    #include <iostream>
    #include <map>
    #include <unordered_map>
    
    #include <QDebug>
    
    using namespace  std;
    
    #define SCREENSHOT_PATH "D:/zhuyunpeng/program/processWater/screenshot.png"
    #define OUTFILE_PATH "D:/zhuyunpeng/program/processWater/test.png"
    
    #define TUBE_COLOR QColor(192, 192, 192, 255)
    #define VIS_TUBE_COLOR QColor(0, 0, 0, 255)
    #define DEFAULE_BACKGROUND_COLOR QColor(239, 250, 229, 255)
    
    struct Tube{
        
        int id;                     // 试管编号
        unsigned int color[4];      // 试管存放的各颜色的液体
        int size;                   // 试管当前的存放的液体数量
        QPoint position;            // 试管在图像上的位置
    
        bool operator <(const Tube &t)const{
        
            return size < t.size;
        }
    };
    
    struct Step{
        
        QPoint click1;              // 第一次点击的位置
        QPoint click2;              // 第二次点击的位置
    };
    
    bool cmpQPoint(const QPoint a, const QPoint b){
        
        if(a.x() == b.x()) return a.y() < b.y();
        return a.x() < b.x();
    }
    
    // 打印所有试管数据
    void printTubes(const QVector<Tube> tubes)
    {
        
        for(const Tube &tube : tubes)
        {
        
            for(int i = 0;i < tube.size; i++)
            {
        
                std::cout << tube.color[i] << " ";
            }
            std::cout << std::endl;
        }
    
        printf("\n\n\n");
    }
    
    /*!
     * \brief 获取试管的中心
     * \details 根据试管的颜色进行搜索，计算试管的位置
     * \return  各个试管外接矩形的中心
     */
    QVector<QPoint> getTubeCenter(QImage &image)
    {
        
        QVector<QPoint> res;
        int w = image.width();
        int h = image.height();
        int dx[4] = {
        0, -1, 0, 1};
        int dy[4] = {
        -1, 0, 1, 0};
    
        for(int i = 0;i < w; ++i)
        {
        
            for(int j = 0;j < h; ++j)
            {
        
                QColor pColor = image.pixelColor(i, j);
                int cnt = 1;
                if(pColor == TUBE_COLOR)
                {
        
                    QPoint leftTop(i, j);
                    QPoint rightButtom(i, j);
                    QQueue<QPoint> que;
                    que.push_back(QPoint(i, j));
                    image.setPixelColor(i, j, VIS_TUBE_COLOR);
                    while(que.count()){
        
                        // qDebug() << que.count() << endl;
                        QPoint p = que.front();
                        que.pop_front();
    
                        // qDebug() << image.pixelColor(p).blue();
                        for(int d = 0; d < 4; ++d)
                        {
        
                            int xx = p.x() + dx[d];
                            int yy = p.y() + dy[d];
                            QColor tc = image.pixelColor(xx, yy);
                            if(xx < 0 || yy < 0 || xx >= w || yy >= h || !(tc == TUBE_COLOR)) continue;
                            que.push_back(QPoint(xx, yy));
                            leftTop.setX(qMin(leftTop.x(), xx));
                            leftTop.setY(qMin(leftTop.y(), yy));
                            rightButtom.setX(qMax(rightButtom.x(), xx));
                            rightButtom.setY(qMax(rightButtom.y(), yy));
                            image.setPixelColor(xx, yy, VIS_TUBE_COLOR);
                            cnt++;
                        }
                    }
                    if(cnt > 200)
                    {
        
                        res.push_back(QPoint((leftTop.x() + rightButtom.x()) / 2,
                                             (leftTop.y() + rightButtom.y()) / 2));
                    }
                }
            }
        }
        return res;
    }
    
    /*!
     * \brief 从(i,j)开始搜索，将相同颜色归类，目的是确定矩形色块的位置
     * \return 所有和（i，j）处相连，且是统一颜色的像素的位置
     */
    QVector<QPoint> findColor(QImage image, int i, int j)
    {
        
        int w = image.width();
        int h = image.height();
        int dx[4] = {
        0, -1, 0, 1};
        int dy[4] = {
        -1, 0, 1, 0};
        QVector<QPoint> res;
        QColor flagColor = image.pixelColor(i, j);
        QColor visColor(255-flagColor.red(), 255-flagColor.green(), 255-flagColor.blue(), 255);
        QQueue<QPoint> que;
        que.push_back({
        i, j});
        image.setPixelColor(i, j, visColor);
        res.push_back({
        i, j});
        while(que.size())
        {
        
            QPoint p = que.front();
            que.pop_front();
            for(int d = 0;d < 4; ++d)
            {
        
                int xx = p.x() + dx[d];
                int yy = p.y() + dy[d];
                if(xx < 0 || yy < 0 || xx >= w || yy >= h
                        || image.pixelColor(xx, yy) != flagColor) continue;
                image.setPixelColor(xx, yy, visColor);
                que.push_back({
        xx, yy});
                res.push_back({
        xx, yy});
            }
        }
        return res;
    }
    
    QVector<QPoint> findColor(QImage image, QPoint p)
    {
        
        return findColor(image, p.x(), p.y());
    }
    /*!
     * \brief 判断是否已经结束倒水
     */
    bool isEnd(const QVector<Tube> &tubes)
    {
        
        for(const Tube &tube : tubes)
        {
        
            if(tube.size > 0 && tube.size < 4)
                return false;
            if(tube.size == 0)
                continue;
            if(tube.size == 4)
            {
        
                if(tube.color[0] == tube.color[1]
                        && tube.color[1] == tube.color[2]
                        && tube.color[2] == tube.color[3])
                    continue;
                else
                    return false;
    
            }
        }
        return true;
    }
    
    // 将试管1的水倒入试管2
    void pushWater(Tube &t1, Tube &t2)
    {
        
        if(t2.size == 4 || t1.size == 0) return;
        if(t2.size == 0 || t2.color[t2.size - 1] == t1.color[t1.size - 1])
        {
        
            t2.color[t2.size] = t1.color[t1.size - 1];
            t2.size++;
            t1.size--;
            pushWater(t1, t2);
        }
    }
    
    /*!
     * \brief 深搜寻找解
     */
    bool findSteps(QVector<Tube> &tubes, map<QVector<Tube>, bool> &vis, QVector<Step> &steps, int deep)
    {
        
        if(deep > 500) return false;
        if(isEnd(tubes))
            return true;
        if(vis.find(tubes) != vis.end()) return false;
        vis[tubes] = true;
    
        for(int i = 0;i < tubes.size(); ++i)
        {
        
            if(tubes[i].size == 0) continue;
            bool colorOver1 = false; // 是否超过1种颜色
            for(int k = 1;k < tubes[i].size; ++k)
            {
        
                if(tubes[i].color[k] != tubes[i].color[k - 1])
                    colorOver1 = true;
            }
    
            for(int j = 0;j < tubes.size(); ++j)
            {
        
                if(i == j) continue;
                if(tubes[j].size == 4) continue;
                // 如果试管中的颜色只有一种，则不允许与一个空试管进行交换
                if(tubes[j].size == 0 && !colorOver1) continue;
                if(tubes[j].size == 0 ||
                        tubes[j].color[tubes[j].size - 1] == tubes[i].color[tubes[i].size - 1])
                {
        
    
                    Tube tubei = tubes[i];
                    Tube tubej = tubes[j];
    
                    steps.push_back({
        tubes[i].position, tubes[j].position});
                    pushWater(tubes[i], tubes[j]);
    
                    // 剪枝：强制同颜色的水倒完
                    bool flag = true;
                    flag = (tubes[i].size > 0 &&
                            tubes[i].color[tubes[i].size - 1] != tubes[j].color[tubes[j].size - 1])
                            || tubes[i].size == 0;
                    if(flag && findSteps(tubes, vis, steps, deep + 1))
                    {
        
                        return true;
                    }
                    steps.pop_back();
                    tubes[i] = tubei;
                    tubes[j] = tubej;
                }
            }
        }
        return false;
    }
    
    int main(int argc, char *argv[])
    {
        
        //获取手机屏幕
        system("D:/zhuyunpeng/program/processWater/screenshot.bat");
        QThread::sleep(3);
    
        QGuiApplication a(argc, argv);
        QImage sFile(SCREENSHOT_PATH);
    
        // test
        // QPainter painter(&sFile);
    
        // 数据存储
        QVector<Tube> tubes;
        map<QVector<Tube>, bool> visState;
    
        // 解析图像
        // 识别试管的位置和数量
        QVector<QPoint> tubesPostion = getTubeCenter(sFile);
    
        qDebug() << "一共有 " << tubesPostion.size() << " 个试管";
           // 初始化试管
        for(int i = 0;i < tubesPostion.size(); ++i)
        {
        
            Tube tube;
            tube.id = i;
            tube.position = tubesPostion[i];
            // 解析试管中的颜色和容量
            QPoint keyPoints[4] = {
        
                {
        tube.position.x(), tube.position.y() + 165},
                {
        tube.position.x(), tube.position.y() + 75},
                {
        tube.position.x(), tube.position.y() - 25},
                {
        tube.position.x(), tube.position.y() - 120}
            };
    
            tube.size = 0;
            for(int j = 0;j < 4; ++j)
            {
        
                QPoint keyPoint = keyPoints[j];
                QColor pColor = sFile.pixelColor(keyPoint);
                QVector<QPoint> points = findColor(sFile, keyPoint);
    
                // 认为大于9000的色块是有效试管颜色
                if(points.size() >= 9000)
                {
        
                    tube.color[tube.size++] = (unsigned int)pColor.rgba();
                }else{
        
                    break;
                }
            }
    
            tubes.push_back(tube);
        }
    
        // 输出各个试管内的颜色情况
        for(int i = 0;i < tubes.size(); ++i){
        
            Tube &tube = tubes[i];
            qDebug() << "第" << i <<"个试管内的情况: "
                     << "position=(" << tube.position.x() << ", " << tube.position.y() << ") "
                     << "size = " << tube.size;
            for(int j = tube.size - 1;j >= 0; --j){
        
                qDebug() << tube.color[j] << " ";
            }
        }
    
        // sFile.save(OUTFILE_PATH);
        // 生成试管倒水的移动方案
        QVector<Step> steps;
        if(findSteps(tubes, visState, steps, 1))
        {
        
            qDebug() << "已找到解决方案! 步骤数=" << steps.size();
        }else{
        
            qDebug() << "未找到解决方案! 步骤数=" << steps.size();
        }
    
        // 执行方案
        // 将互不影响的试管方案并发执行
        QVector<Step> runSteps;
    
        for(int i = 0;i < steps.size(); ++i){
        
            Step &step = steps[i];
            if(runSteps.size())
            {
        
                bool canRun = true;
                for(Step &s : runSteps){
        
                    // 将互不影响的方案并发执行
                    if(s.click1 == steps[i].click1
                            || s.click1 == steps[i].click2
                            || s.click2 == steps[i].click1)
                    {
        
                        canRun = false;
                        break;
                    }
                }
                if(!canRun){
        
                    runSteps.clear();
                    QThread::sleep(3);
                }
            }
            runSteps.push_back(steps[i]);
            qDebug() << "from (" << step.click1.x() << ", " << step.click1.y() << ")"
                     << "to (" << step.click2.x() << ", " << step.click2.y() << ")";
            QString cmd1 = QString("adb shell input tap %1 %2")
                    .arg(step.click1.x()).arg(step.click1.y());
            system(cmd1.toStdString().c_str());
            QThread::msleep(100);
    
            QString cmd2 = QString("adb shell input tap %1 %2")
                    .arg(step.click2.x()).arg(step.click2.y());
            system(cmd2.toStdString().c_str());
            // QThread::sleep(3);
        }
    
        return 0;
    }

[8bd0e4ad6c144687bf74986450869f0d.gif_pic_center]: /images/20220828/7a1e374523e841aab62f808eef00ea4b.png