首页 > 试题广场 >

寻找十字

[编程题]寻找十字
  • 热度指数：92 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小图最近非常喜欢玩一个游戏。游戏的规则是，在一个n*m大小的0/1矩阵中，找到如下的图形：
?1?
111
?1?
其中?位置可以是0也可以是1。

游戏中，小图需要指出在给出的0/1矩阵中这个图形出现在了多少个不同的位置。
现在他希望你可以写一个程序帮助他计算这个值。

输入描述:
输入的第一行是两个正整数n, m，1 <= n, m <= 1000。

接下来的n行，每行有m个字符，每个字符是0或1中的一个，表示了整个0/1矩阵。


输出描述:
输出只包含一个正整数，为输入的0/1矩阵中有多少个不同位置的上述图形。
示例1

输入

5 5
01000
11100
11101
11111
00101

输出

3

说明

样例中总共有三个不同的图形，它们的中心分别在：

第2行第2列、第3行第2列、第4行第3列。
算法知识视频讲解
添加回答
牛客811893262号头像 牛客811893262号
注意，这里有个坑，输入数据没有空格隔开，如果定义数据的类型为非char的，输入赋值就会出错。
如对于例子中的数据，int maps[n][m]，则cin>>maps[i][j]时 有maps[0][0]=01000 map[0][1]=11000...而非maps[0][0]=0,maps[0][1]=1.... 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    char maps[n][m];
    int cnt = 0;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> maps[i][j];
        }
    }

    for (int i = 1; i < n - 1; ++i)
    {
        for (int j = 1; j < m - 1; ++j)
        {
            if (maps[i][j] == '1')
            {
                if (maps[i - 1][j] == '1' && maps[i + 1][j] == '1' && maps[i][j - 1] == '1' && maps[i][j + 1] == '1')
                {
                    ++cnt;
                }
            }
        }
    }
    cout << cnt << endl;
}



发表于 2020-05-21 15:29:16 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 图森未来 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
1条回答 1489浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号