No.3813 Ashwreath
レベル :
/ AI推定難易度 : 2000
/ 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 :
dyktr_06
/ テスター :
sepa38
tyawanmusi
タグ : / 解いたユーザー数 8
作問者 :
sepa38
問題文最終更新日: 2026-09-21 06:54:45
yukicoder contest 524
(順位表)
の他の問題:
問題文
$N \times M$ のグリッド $S$ があります。
$S_{i,j}$ が . のマスは空きマスであり、# のマスは火がついているマスです。
空きマスをいくつか選び、選んだ各マスに植物を $1$ 個ずつ植えることができます。植えられる植物の個数に制限はありません。
植物を植えた後、以下の条件をすべて満たすマスを良いマスと呼びます。
- 空きマスであるかつ、植物が植えられていない。
- 隣接する $8$ マスのうち、植物が植えられているマスが $2$ 個以上ある。
- 隣接する $8$ マスのうち、火がついているマスが $2$ 個以上ある。
ここで、二つのマスが辺または頂点を共有するとき、それらのマスは隣接しているものとします。グリッドの外側のマスは数えません。
良いマスの個数としてあり得る最大値を求めてください。
制約
- $1 \leq N, M \leq 10$
- $S_{i,j}$ は
.または# - $N, M$ は整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$
出力
良いマスの個数としてあり得る最大値を $1$ 行に出力してください。
サンプル
サンプル1
入力
3 3 ### ... ...
出力
3
上から $3$ 行目のすべてのマスに植物を植えると、上から $2$ 行目のすべてのマスが良いマスになります。
サンプル2
入力
6 7 ####### ....... ....... ....... ....... #######
出力
14
上から $3$ 行目と $4$ 行目のすべてのマスに植物を植えると、上から $2$ 行目と $5$ 行目のすべてのマスが良いマスになります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。