問題は：
Tommy はサイズ N の正方形の家をセルに分割しており、セキュリティのために家の周りにセンサー検出デバイスを配置したいと考えています。各センサーは、置かれた位置から最大 K 歩数を検出できます。家の中には柱であるM個の位置があり、センサーはそれを介して検出できません。彼は最大 5 台のデバイスを配置する予定で、最小数のデバイスを使用して家全体をカバーする方法を考えています。
以下のようにサンプルを視覚化してみましょう (= は空セル、o は極セル)。
=====
うーん==
=====
=おお=
=====
デバイス (D) を位置 (3, 4) に配置すると、デバイス カバレッジは以下のように視覚化されます (各セル内の数字はデバイスからのインスタンスを示します)。
==323
ooo12
321D1
=ooo2
====3
私の質問は：
この問題を解決するための最適なソリューションはありますか?
Set Cover、Exact Coverの問題に関する記事を検索して読みましたが、上記の問題を解決するためにそれを実装する方法を見つけることができませんでした。