The problem is:
Tommy has a square house with size N divided into cell and he want to place sensor detection devices around the house for security. Each sensor can detect up to K step count from the position it is placed. There are M positions inside the house which is pole and sensor can not detect through it. He plans to place at max 5 devices and wondering how to use a minimum number of devices to cover the whole house.
Let visualize the sample like below (= is empty cell and o is pole cell)
=====
ooo==
=====
=ooo=
=====
If he place the device (D) at position (3, 4) the device coverage will be visualized as below (the number inside each cell indicate the instance from the device)
==323
ooo12
321D1
=ooo2
====3
My question is:
Is there any optimal solution to solve this problem?
I have searched and read some article about Set Cover, Exact Cover problem but could not find out the way to implement it to solve the problem above.