menu Error0 Blog
扫雷游戏
26730 浏览 | 2019-08-19 | 分类:算法 | 标签:

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。

现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。

注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
输入描述:

输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。
接下来n行,每行m个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。

输出描述:

输出文件包含n行,每行m个字符,描述整个雷区。用’*’表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

示例1
输入

3 3
*??
???
?*?

输出

*10
221
1*1

示例2
输入

2 3
?*?
*??

输出

2*1
*21

备注:

对于100%的数据,1≤n≤100,1≤m≤100。

代码

#include<iostream>
using namespace std;

int  arr[101][101];
char  map[101][101];
int n, m;
int index[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1 },{1,-1},{-1,1} }; /*方向的差值*/
int dfs(int x, int y)
{
    int sum = 0;
    if (map[x][y]=='*') /*雷没必要计算*/
    {
        return sum;
    }

    for (int i = 0; i< 8; i++)
    {
        int h = x, l = y;
        h +=index[i][0];
        l += index[i][1];
        if (h > n || h<0 || l>m || l < 0) /*范围*/
            continue;
        if (map[h][l] == '*')
        {
            sum++;
        }
    }
    return sum;
}

int main()
{
    cin >> n >> m;
    /*输入数据*/
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
    /*开始计算*/
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            arr[i][j] += dfs(i, j); 
            if (map[i][j] == '*')
            {
                cout << map[i][j];
            }
            else {
                cout << arr[i][j];
            }
        }
        cout << endl;
    }
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89