問題一覧 > 通常問題

No.3813 Ashwreath

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : dyktr_06 / テスター : sepa38 tyawanmusi
お気に入りにしたユーザー ProblemId : 14066 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。