C++笔记-二维棋盘数组转邻接表（使用QTL）

灰太狼 2022-10-10 15:54 88阅读 0赞

使用这样的结构存储邻接表：

QVector<QVector<Point>> m_adj;

Point存储当前顶点号及X轴，Y轴：

struct Point{
    
        Point(int vNum, int x, int y) {
    
            this->vNum = vNum;
            this->x = x;
            this->y = y;
        }
    
        int vNum = -1;		//顶点号
        int x;			//x轴
        int y;			//y轴
    };

这里棋盘是这样的，如下：

#define MAX_COLUMN 6 + 2
    #define MAX_ROW 6 + 2
    
    //棋牌用-1包住，保证处理的统一
    int map1[MAX_ROW][MAX_COLUMN] = {
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, 1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, 1, 0, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1
    };

这里的算法很简单：

//左上
    if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y - 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y - 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //正上
    if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y);
        if (point.vNum != -1) {
    
        //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //右上
    if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y + 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y + 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //正右
    if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y + 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y + 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //右下
    if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y + 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y + 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //正下
    if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //左下
    if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y - 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y - 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
        }
    }
    
    //正左
    if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y - 1] != -1) {
    
        Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y - 1);
        if (point.vNum != -1) {
    
            //顶点是从1开始算，但下标是从0开始
            m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
         }
    }

程序运行截图如下；

这样的棋盘：

int map1[MAX_ROW][MAX_COLUMN] = {
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, 1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, -1, 0, -1, -1, -1, -1, -1,
        -1, 1, 0, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70][]

下面这种棋盘：

int map1[MAX_ROW][MAX_COLUMN] = {
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, 1, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, 1, 0, 1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1
    };

运行截图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70 1][]

完整源码如下：

#include <QDebug>
    #include <QVector>
    
    #define MAX_COLUMN 6 + 2
    #define MAX_ROW 6 + 2
    
    //棋牌用-1包住，保证处理的统一
    int map1[MAX_ROW][MAX_COLUMN] = {
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1,
        -1, -1, -1, -1, -1, -1, 1, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, -1, -1, 0, -1,
        -1, -1, -1, -1, 1, 0, 1, -1,
        -1, -1, -1, -1, -1, -1, -1, -1
    };
    
    struct Point{
    
        Point(int vNum, int x, int y) {
    
            this->vNum = vNum;
            this->x = x;
            this->y = y;
        }
    
        int vNum = -1;		//顶点号
        int x;			//x轴
        int y;			//y轴
    };
    
    class Graph {
    
    public:
        Graph(int map[MAX_ROW][MAX_COLUMN]) {
    
            memcpy(m_map, map, sizeof(m_map));
    
            //不为-1的都是顶点
            int vCount = 0;
    
            for (int i = 0; i < MAX_ROW; i++) {
    
                for (int j = 0; j < MAX_COLUMN; j++) {
    
                    if (map[i][j] != -1) {
    
                        Point point(++vCount, i, j);
                        QVector<Point> ve;
                        ve.append(point);
                        m_adj.append(ve);
                    }
                }
            }
    
            if (vCount == 0) {
    
                qDebug() << "退出" << endl;
                exit(-1);
            }
    
            this->m_v = vCount;
    
            analysisEdge();
        }
    
        //打印邻接表
        void print() {
    
    
            for (int i = 0; i < this->m_v; ++i) {
    
                qDebug() << "顶点:" << this->m_adj[i][0].vNum << " x:" << this->m_adj[i][0].x << " y:" << this->m_adj[i][0].y << " 的邻接表!";
                for (int j = 0; j < this->m_adj[i].size(); j++) {
    
                    qDebug() << "顶点:" << this->m_adj[i][j].vNum << " x:" << this->m_adj[i][j].x << " y:" << this->m_adj[i][j].y;
                }
    
                qDebug() << "------------------------------------";
            }
        }
    
    protected:
    
        //通过坐标获取顶点号
        Point getPointByPosXAndPosY(int x, int y) {
    
            for (int i = 0; i < this->m_v; i++) {
    
                if (this->m_adj[i][0].x == x && this->m_adj[i][0].y == y) {
    
                    return this->m_adj[i][0];
                }
            }
    
            return Point(-1, -1, -1);
        }
    
        void analysisEdge() {
    
            //分析下边，这个顶点，如果周围一圈都是非-1的数，说明都可达。
            for (int i = 0; i < this->m_v; i++) {
    
    
                //左上
                if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y - 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y - 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //正上
                if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //右上
                if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y + 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y + 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //正右
                if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y + 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y + 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //右下
                if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y + 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y + 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //正下
                if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //左下
                if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y - 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y - 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
    
                //正左
                if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y - 1] != -1) {
    
                    Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y - 1);
                    if (point.vNum != -1) {
    
                        //顶点是从1开始算，但下标是从0开始
                        m_adj[this->m_adj[i][0].vNum - 1].push_back(point);
                    }
                }
            }
        }
    
    
    private:
        int m_v;	//顶点的个数
        int m_map[MAX_ROW][MAX_COLUMN];
        QVector<QVector<Point>> m_adj;
    };
    
    
    
    int main(int argc, char *argv[]) {
    
        Graph g(map1);
    
        g.print();
    
        getchar();
        return 0;
    }

还有一种是用-1包住棋盘，这样就更加方便了，在下一篇笔记中将会说明！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70]: /images/20221005/2969a435d02443788ef5cbe74b9a8d42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70 1]: /images/20221005/abddf6c1270046e5877265c4c06a9e35.png