Securing the Palace

Once upon a time there was a King who was really paranoid about the safety of his grand palace. The map of the palace can be described by a matrix with N rows and M columns. Each cell of the matrix encodes either a wall, or free space, where trophies, jewellery and precious fur can be stored. During the last replanning of the palace, it was divided into a number of rooms, each of which has a rec