CF1059B.Forgery
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn't give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor's handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor's signature is impossible to forge. Or is it?
For simplicity, the signature is represented as an n×m grid, where every cell is either filled with ink or empty. Andrey's pen can fill a 3×3 square without its central cell if it is completely contained inside the grid, as shown below.
xxx
x.x
xxx
Determine whether is it possible to forge the signature on an empty n×m grid.
学生安德烈整个学期都逃掉了体育课,现在他必须设法在这门课上获得及格成绩。显然,通过合法途径是不可能做到这一点的,但安德烈并不放弃。他从当地医院弄来了一份空白证明,打算利用自己对当地医生笔迹的了解,伪造一份病假证明。然而,在写完证明的大部分内容后,安德烈突然发现医生的签名根本无法模仿——真的无法模仿吗?
为简化问题,该签名被表示为一个 n×m 的网格,其中每个格子要么被墨水填满,要么为空。安德烈的笔每次可以在网格内完整包含的前提下,填充一个 3×3 方形区域(除其中心格子外),如下图所示:
xxx
x.x
xxx
试判断:能否在初始全为空的 n×m 网格上,通过若干次上述操作,恰好伪造出目标签名?
输入格式
The first line of input contains two integers n and m (3≤n,m≤1000).
Then n lines follow, each contains m characters. Each of the characters is either '.', representing an empty cell, or '#', representing an ink filled cell.
输入的第一行包含两个整数 n 和 m(3≤n,m≤1000)。
接下来是 n 行,每行包含 m 个字符。每个字符要么是 '.',表示一个空单元格;要么是 '#',表示一个被墨水填充的单元格。
输出格式
If Andrey can forge the signature, output "YES". Otherwise output "NO".
You can print each letter in any case (upper or lower).
如果 Andrey 能够伪造签名,则输出 “YES”;否则输出 “NO”。
您可以以任意大小写(大写或小写)输出每个字母。
输入输出样例
输入#1
3 3 ### #.# ###
输出#1
YES
输入#2
3 3 ### ### ###
输出#2
NO
输入#3
4 3 ### ### ### ###
输出#3
YES
输入#4
5 7 ....... .#####. .#.#.#. .#####. .......
输出#4
YES
说明/提示
In the first sample Andrey can paint the border of the square with the center in (2,2).
In the second sample the signature is impossible to forge.
In the third sample Andrey can paint the borders of the squares with the centers in (2,2) and (3,2):
-
we have a clear paper:
...
...
...
... -
use the pen with center at (2,2).
#.#
...
-
use the pen with center at (3,2).
In the fourth sample Andrey can paint the borders of the squares with the centers in (3,3) and (3,5).
在第一个样例中,安德烈可以绘制以 (2,2) 为中心的正方形的边框。
在第二个样例中,该签名无法伪造。
在第三个样例中,安德烈可以绘制以 (2,2) 和 (3,2) 为中心的两个正方形的边框:
-
初始纸张为空白:
...
...
...
... -
使用以 (2,2) 为中心的画笔。
#.#
...
-
使用以 (3,2) 为中心的画笔。
在第四个样例中,安德烈可以绘制以 (3,3) 和 (3,5) 为中心的两个正方形的边框。
输入解题思路,AI测评打分。不知道怎么写?