/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君は、ある会社のネットワーク管理者です。彼は社内ネットワークのセキュリティ診断を行っています。
社内ネットワークは N 行 M 列のグリッド状に配置されたサーバールームで構成されています。各部屋にはサーバーが設置されているか、空き部屋になっています。サーバーが設置された部屋は # 、空き部屋は . で表されます。
サーバーが設置された部屋について、グリッド内に存在する上下左右に隣接する部屋のうち、サーバーが設置されている部屋の数を「隣接サーバー数」と呼びます。グリッドの外側には部屋は存在しないため、隣接サーバー数を数える際にはグリッドの外側は考慮しません。
隣接サーバー数が 0 のサーバーは孤立しており障害時の冗長性がなく、隣接サーバー数が 4 のサーバーは負荷が集中しすぎるため、いずれもセキュリティ上問題があるとされています。そこでセキュリティポリシーでは、以下の条件を定めています：
- すべてのサーバーについて、隣接サーバー数が 1 以上 3 以下である。
高橋君は現在のネットワーク配置図を渡され、この配置がセキュリティポリシーを満たしているかどうかを判定することになりました。
与えられたネットワーク配置がセキュリティポリシーの条件を満たしているかどうかを判定してください。なお、サーバーが 1 つも設置されていない場合は、条件に違反するサーバーが存在しないため、セキュリティポリシーを満たしているものとします。
制約
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- S_i（1 \leq i \leq N）は
#と.のみからなる長さ M の文字列である
入力
N M S_1 S_2 \vdots S_N
- 1 行目には、グリッドの行数を表す整数 N と列数を表す整数 M が、スペース区切りで与えられる。
- 続く N 行のうち i 行目（1 \leq i \leq N）には、グリッドの上から i 行目の状態を表す長さ M の文字列 S_i が与えられる。各文字は
#（サーバー）または.（空き部屋）である。
出力
ネットワーク配置がセキュリティポリシーの条件を満たしている場合は Yes を、満たしていない場合は No を 1 行で出力せよ。
入力例 1
3 3 .#. ### .#.
出力例 1
No
入力例 2
4 5 ..... .#.#. .###. .....
出力例 2
Yes
入力例 3
5 8 ........ .##.###. .##.#.#. ....###. ........
出力例 3
Yes
Score : 266 pts
Problem Statement
Takahashi is a network administrator at a company. He is conducting a security assessment of the company's internal network.
The internal network consists of server rooms arranged in a grid of N rows and M columns. Each room either contains a server or is empty. A room with a server is represented by #, and an empty room is represented by ..
For each room containing a server, the number of adjacent rooms (up, down, left, right) within the grid that also contain servers is called the "adjacent server count". Since no rooms exist outside the grid, rooms outside the grid are not considered when counting adjacent servers.
A server with an adjacent server count of 0 is isolated and lacks redundancy in case of failure, while a server with an adjacent server count of 4 has too much load concentrated on it. Both cases are considered security risks. Therefore, the security policy defines the following condition:
- For every server, the adjacent server count must be at least 1 and at most 3.
Takahashi has been given the current network layout and must determine whether this layout satisfies the security policy.
Determine whether the given network layout satisfies the security policy condition. Note that if no servers are installed at all, there are no servers violating the condition, so the security policy is considered satisfied.
Constraints
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- S_i (1 \leq i \leq N) is a string of length M consisting only of
#and.
Input
N M S_1 S_2 \vdots S_N
- The first line contains an integer N representing the number of rows and an integer M representing the number of columns of the grid, separated by a space.
- The following N lines each contain a string S_i of length M (1 \leq i \leq N), representing the state of the i-th row from the top of the grid. Each character is either
#(server) or.(empty room).
Output
If the network layout satisfies the security policy condition, output Yes; otherwise, output No, on a single line.
Sample Input 1
3 3 .#. ### .#.
Sample Output 1
No
Sample Input 2
4 5 ..... .#.#. .###. .....
Sample Output 2
Yes
Sample Input 3
5 8 ........ .##.###. .##.#.#. ....###. ........
Sample Output 3
Yes