首页 > 试题广场 >

剪纸游戏

[编程题]剪纸游戏

热度指数：357 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小蓝拿着一张 $n \times m$ 的方格纸从中剪下若干不相连的图案；剪裁时只会沿着方格网线裁切，因此不会破坏任何一个完整的小方格。

$\hspace{15pt}$ 小灰灰只拿到了剩余的残缺纸张。若用 `'.'` 表示被剪去的小方格，`'*'` 表示仍保留的小方格，则他得到一张由 `'.'` 与 `'*'` 组成的矩阵。由于各个剪下的图案之间互不连通，小灰灰可以根据 `'.'` 的连通块反推出每一个被剪下来的图案。

$\hspace{15pt}$ 现在小灰灰想知道：在所有被剪下来的图案中，有多少个是长方形（正方形视为特殊的长方形）。

输入描述:

第一行输入两个整数 ——纸张的行数与列数。
接下来  行，每行输入一个长度为  的由 `'.'` 与 `'*'` 组成的字符串，描述残缺纸张的形状：
`'.'` 代表该方格已被剪去；
`'*'` 代表该方格仍保留。

输出描述:

输出一个整数，表示被剪下来的图案中长方形的数量。

示例1

输入

4 10
*.*.*...**
...***.*..
.**..*.*..
*..*****..

输出

说明


可以看出，图中恰有一个正方形，三个长方形，共计四个长方形。

算法知识视频讲解

原神大学

发表于 2024-01-20 13:53:31

链接https://ac.nowcoder.com/acm/contest/73450/D 这道题直接用BFS把所有连通块找出来，将每一个连通块的最大最小的x轴与y轴坐标记录下来，遍历这四个点所包含的区域，看是否有'*'就行了，下面是代码。 #include<bits/stdc++.h> 展开全文

lovejsn

发表于 2024-01-19 22:25:12

链接https://ac.nowcoder.com/acm/contest/73450/D 题目如上。此题考查一个图的深度或者广度优先遍历。此题的难点在于判断是否是一个长方形，我是在广度优先的时候记录了所走过的方块数量cnt,和所有点的最大最小横纵坐标，即maxi,maxj,mini,minj, 展开全文

ikun_ac

发表于 2025-08-08 23:58:52

题目链接剪纸游戏题目描述给定一张由 '.' 与 '*' 组成的矩阵，'.' 表示被剪去的小方格，'*' 表示仍保留的小方格。'.' 的每个连通块（按四方向连通）对应一个被剪下的图案。问被剪下来的图案中，有多少个是长方形（正方形视为特殊的长方形）。输入：第一行两个整数：、接下来行展开全文

丨阿伟丨

发表于 2025-08-29 11:46:09

题目链接剪纸游戏题目描述在一张由 . 和 * 组成的网格纸上，. 代表被剪去的小方格，* 代表保留的小方格。被剪下的图案都是由 . 构成的、互相不连通的区域。你需要计算，在所有被剪下来的图案中，有多少个是长方形（正方形被视为特殊的长方形）。解题思路这个问题可以分解为两个主要步骤：找展开全文

问题信息

广度优先搜索(BFS)

难度：

1条回答 5收藏 60浏览

剪纸游戏

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题