C++笔记-二维棋盘数组使用BFS（宽度优先遍历）

痛定思痛。 2022-10-10 15:54 103阅读 0赞

这里只对一个顶点只能上下左右，不能和左上，左下，右上，右下连起来。

思路步骤：

1.二维棋盘数据转链接表；

2.邻接表直接进行BFS

源码如下：

#include <QDebug>
    #include <QVector>
    #include <QQueue>
    
    #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, 1, 0, -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轴
    
        friend QDebug operator << (QDebug os, Point &test){
    
            os << "(顶点:" << test.vNum << ", x:" << test.x << ", y:" << test.y << ")";
            return os;
        }
    };
    
    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() << "------------------------------------";
            }
        }
    
        void bfs(int startV){
    
            bool visited[this->m_v];
    
            for(int i = 0; i < this->m_v; i++){
    
                visited[i] = false;
            }
    
            Point point = getPointByVertex(startV);
            if(point.vNum == -1){
    
                qDebug() << "顶点错误!";
                exit(0);
            }
    
            QQueue<Point> queue;
            queue.push_back(point);
            visited[startV] = true;
    
            while(!queue.empty()){
    
                Point s = queue.front();
                queue.pop_front();
    
                // start todo something
                qDebug() << s;
    
                // end todo something
    
                for(int i = 0; i < this->m_adj[s.vNum].size(); i++){
    
                    int curretV = this->m_adj[s.vNum][i].vNum;
                    if(visited[curretV] == false){
    
                        visited[curretV] = true;
                        queue.push_back(this->m_adj[s.vNum][i]);
                    }
                }
            }
        }
    
    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);
        }
    
        //通过顶点号返回Point
        Point getPointByVertex(int v){
    
            for(int i = 0; i < this->m_v; i++){
    
                if(this->m_adj[i][0].vNum == v){
    
                    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].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].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].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].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].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].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].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].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[]) {
    
        Q_UNUSED(argc)
        Q_UNUSED(argv)
    
        Graph g(map1);
    
        g.print();
        g.bfs(0);
    
        getchar();
        return 0;
    }

如下二维棋盘：

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, 1, 0, -1,
        -1, -1, -1, -1, -1, -1, -1, -1
    };

BFS是这样的（从第1个顶点（下标为0）开始）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70]: /images/20221005/d1d2ee95afda44168c5e6a9bab7fe1e1.png