[数据结构与算法]《扫雷》游戏初始化数据算法分析

数据初始化，可以分为两个步骤。第一个步骤就是随即生成雷的位置，第二个步骤就是根据雷的位置计算每一个非雷的方格的雷的数量。

LeiStatus：雷的状态，在整个方格中他只有两种可能，要么他是雷，要么他是数字。如果什么都不显示，其实他是数字0.

数据结构说明

struct Block {
    int x;
    int y;
};

enum LeiStatus { isNum = 0, isLei };

enum ShowStatus {
    hideNum = 0,
    showNum,
    isOk,  // 确认这个是雷,即给这个格子标上小旗
    isAsk  // 不确定这个是什么，给这个格子标上问号

};

/**
 * @brief The Cell 每一个格子的结构体
 */
struct Cell : Block {
    LeiStatus leiStatus;
    ShowStatus showStatus;
    int num;  // 表示每个位置的上下左右八个位置的雷的数据，如果雷的状态是
    Cell()
    {
        leiStatus = isNum;
        num = 0;
        showStatus = hideNum;
    }
};

第一步：初始化化雷的位置。

    // 1.根据横纵坐标的最大值生成，方格。   
    for (int i = 0; i < m_max_block_y; i++) {
        for (int j = 0; j < m_max_block_x; j++) {
            Cell lei;
            lei.x = i;
            lei.y = j;
            m_cells.push_back(lei);
        }
    }
    
    // 2. 初始化雷的位置
    int sum = 0;
    int size = m_cells.size();
    
    do {
        int ran = getRandom(size);
        // 为避免雷的位置会出现重复，导致数量方格内的雷的数量不达标，因此在生成随机数后需要对该位置进行判断是否已经是雷。如果是雷那么+1
        if (m_cells.at(ran).leiStatus != isLei) {
            sum++;
            m_cells[ran].leiStatus = isLei;
        }
    } while (sum < m_sum_lei);

?

第二步：计算每个方格的雷的总数

  // 初始化个个数据
    for (int i = 0; i < m_cells.size(); i++) {
        // 如果这个位置是雷就不需要统计了
        if (m_cells[i].leiStatus == isLei) continue;
        int sum = sumLeiStatus(m_cells[i].x, m_cells[i].y, isLei);
        m_cells[i].num = sum;
    }
 // 根据当前位置计算当前位置的8个角的总数。
int QGameWidget::sumLeiStatus(int block_x, int block_y, LeiStatus leiStatus)
{
    int sum = 0;
    int b_x = block_x;
    int b_y = block_y;

    // 左上角
    if (b_x - 1 >= 0 && b_y - 1 >= 0) {
        if (m_cells.at(getIndex(b_x - 1, b_y - 1)).leiStatus == leiStatus) {
            sum++;
        }
    }
    // 正上
    if (b_y - 1 >= 0) {
        if (m_cells.at(getIndex(b_x, b_y - 1)).leiStatus == leiStatus) {
            sum++;
        }
    }
    // 右上角
    if (b_x + 1 < m_max_block_x && b_y - 1 >= 0) {
        if (m_cells.at(getIndex(b_x + 1, b_y - 1)).leiStatus == leiStatus) {
            sum++;
        }
    }
    // 正右
    if (b_x + 1 < m_max_block_x) {
        if (m_cells.at(getIndex(b_x + 1, b_y)).leiStatus == leiStatus) {
            sum++;
        }
    }

    // 右下
    if (b_x + 1 < m_max_block_x && b_y + 1 < m_max_block_y) {
        if (m_cells.at(getIndex(b_x + 1, b_y + 1)).leiStatus == leiStatus) {
            sum++;
        }
    }

    // 正下
    if (b_y + 1 < m_max_block_y) {
        if (m_cells.at(getIndex(block_x, block_y + 1)).leiStatus == leiStatus) {
            sum++;
        }
    }
    //左下
    if (b_x - 1 >= 0 && b_y + 1 < m_max_block_y) {
        if (m_cells.at(getIndex(b_x - 1, b_y + 1)).leiStatus == leiStatus) {
            sum++;
        }
    }
    // 左
    if (b_x - 1 >= 0) {
        if (m_cells.at(getIndex(b_x - 1, b_y)).leiStatus == leiStatus) {
            sum++;
        }
    }
    return sum;
}

以上代码可以优化成

int QGameWidget::sumLeiStatus(int block_x, int block_y, LeiStatus leiStatus)
{
    int sum = 0;
    int b_x = block_x;
    int b_y = block_y;

    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (i == 0 && j == 0) {
                continue;
            }
            int index = getIndex(b_x - i, b_y - j);
            if (index < 0) {
                continue;
            }
            if (m_cells.at(index).leiStatus == leiStatus) {
                sum++;
            }
        }
    }
    return sum;
}
int QGameWidget::getIndex(int block_x, int block_y)
{
    if (block_x < 0 || block_y < 0) return -1;
    if (block_x >= m_max_block_x || block_y >= m_max_block_y) return -2;
    return block_x * m_max_block_x + block_y;
}