C语言—-扫雷游戏

扫雷游戏本题设置了四个规则：

1，如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X' 。

2，如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
3，如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。

4，如果在此次点击中，若无更多方块可被揭露，则返回盘面。

 解题思路：

1，从给出的点出发，如果该点很不幸就是雷，置为'X'，game over，匹配规则1,

2，不是雷的情况，采用深度搜索算法(dfs)，对于当前点，如果为'E'说明没有被涉足，我们扫描以该点为中心的九宫格，统计雷的个数count(即字符'M'的个数)

3，如果count为0，说明没有雷，将'E'置为'B'，匹配规则2；

4，如果count不为0，说明有雷，置为count数，并且从该点出发搜索九宫格，匹配规则3

 代码如下：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void dfs(char** board, int x, int y, int boardSize, int boardColSize)
{
    if(x<0 || x>=boardSize || y<0 || y>=boardColSize || board[x][y] != 'E') //首先对当前搜索的点(x,y)做合法性检查，保证在搜索的区域内
        return;
    int count = 0;
    int i,dx,dy;
    int x_dir[8] = {-1,0,1,-1,1,-1,0,1};//八个方向搜索
    int y_dir[8] = {1,1,1,0,0,-1,-1,-1};
    for(i=0; i<8; i++)
    {
        dx = x + x_dir[i];
        dy = y + y_dir[i];
        if(dx<0 || dx>=boardSize || dy<0 || dy>=boardColSize)
            continue;
        else if(board[dx][dy] == 'M')   //如果是雷，则统计雷的个数
            count++;
    }
    if(count != 0)   //如果count不为0,说明周边有雷，匹配规则3后返回
        board[x][y] = count + '0';
    else
    {   //如果count为0,说明周边没有雷，匹配规则2，以该点为中心继续搜索，八个方向搜索完后返回
        board[x][y] = 'B';
        for(i=0; i<8; i++)
        {
            dx = x + x_dir[i];
            dy = y + y_dir[i];
            dfs(board,dx,dy,boardSize,boardColSize);
        }
    }
    return;
}

char** updateBoard(char** board, int boardSize, int* boardColSize, int* click, int clickSize, int* returnSize, int** returnColumnSizes)
{
    int click_x = click[0];
    int click_y = click[1];
    if(board[click_x][click_y] == 'M')  //匹配规则1
        board[click_x][click_y] = 'X';
    else
        dfs(board,click_x,click_y,boardSize,boardColSize[0]);
        
    *returnSize = boardSize;
    (*returnColumnSizes) = (int*)malloc(sizeof(int)*boardSize);
    for(int i=0; i < boardSize; ++i)
        (*returnColumnSizes)[i] = boardColSize[0];

    return board;
}

运行结果：