| 题目名称 | 3588. [HAOI 2021PJ]水儿的绘画 |
|---|---|
| 输入输出 | haoi2021pj_paint.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2021-04-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：35， 通过率：25.71% | ||||
 yrtiop |
100 | 0.000 s | 0.00 MiB | C++ |
 数声风笛ovo |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
OTTF |
100 | 0.000 s | 0.00 MiB | C++ |
|
nichengyan |
100 | 0.000 s | 0.00 MiB | C++ |
|
nichengyan |
100 | 0.000 s | 0.00 MiB | C++ |
|
tinker |
100 | 0.000 s | 0.00 MiB | C++ |
|
wzprogrammer_X |
100 | 0.000 s | 0.00 MiB | C++ |
|
ムラサメ |
100 | 0.000 s | 0.00 MiB | C++ |
|
nichengyan |
90 | 0.000 s | 0.00 MiB | C++ |
| 关于 水儿的绘画 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
好题，很有价值
低调
2023-02-18 21:25
3楼
| ||||
|
floodfill+暴力枚举居然都能过，本来还以为要BFS。。
| ||||
|
冰儿？
 康尚诚
2021-04-12 20:31
1楼
| ||||
3588. [HAOI 2021PJ]水儿的绘画
★☆ 输入文件：haoi2021pj_paint.in
输出文件：haoi2021pj_paint.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
听说最新的流行趋势绘画册是一张图画上有两片连续图案，水儿画了一大堆两片图案的图画。不幸的是，时尚潮流往往变化很快，而且最流行的时尚变成是只有一片图案的图画！
水儿想让她的画更时尚，把她的每一幅画挂在在墙上，想把两片连续图案合为一片图案的方法。水儿的画用N乘M（1<=N，M<=50）的字符网格表示，如下所示：
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....
这里，每个“X”表示一片图案的一部分。两个X属于同一片图案,条件是如果它们是垂直或水平相邻的（对角线相邻则不是），所以上面的图画正好有两片图案。水儿所有的画都正好有两片图案。
水儿想用尽可能少的颜料把这两片图案合并成一大片图案。在上面的例子中，他可以画三个带有“X”的附加字符（新字符用“*”标记，以便于查看）。
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX....
请帮助水儿确定她必须画的新“X”的最小数量,把两片图案合并成一大片图案。
【输入格式】
第1行：两个整数N,M,用一个空格隔开；
第2～N+1行:每行是一个长度为M的，由"X"和"."组成的字符串;
【输出格式】
共一行，一个整数，表示必须添加到输入图案中的新“X”的最小数目。
【样例输入】
6 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....
【样例输出】
3
【提示】
输入数据显示了一幅图画，上面有两片不同的图案，分别用1和2标记：
................ ..1111....222... ...1111....22... .1111......222.. ........22222... .........222....三个'X'就足够把两片图案连在一起了：
................ ..1111....222... ...1111X...22... .1111..XX..222.. ........22222... .........222....
【来源】
2021年河南省青少年程序设计能力认证 Task4