#include
#include
using?namespace?std;

class?Monitor{
????int?mn;//矩陣的大小
????char?**Matrix;//矩陣
????int?*Place;//監控所放置的位置
public:
????Monitor（）{}
????Monitor（int?mint?n）{
????????int?ijroomxy;
????????this->m?=?m;
????????this->n?=?n;

????????Matrix?=?new?char?*[m];
????????for（i?=?0;?i?????????????Matrix[i]?=?new?char?[n];
????????room?=?m?*?n;
????????Place?=?new?int?[room];
????????for（i?=?0;?i?????????????for（j?=?0;?j?????????????????Matrix[i][j]?=?0;

????????????i?=?room?/?5;//min是在此矩陣內所需要的最少監控數量
????????????if（room?%?5）
????????????????i++;//剪枝策略1
????????????for（;?i?????????????????for（j?=?0;?j?????????????????????SetMonitor（-4j）;//-4表示沒有監控需要拆除
????????????????while（j?????????????????????Place[j++]?=?0;
????????????????if（Prem_Modify（i?-?1room））
????????????????????break;
????????????????for（x?=?0;?x?????????????????????for（y?=?0;?y?????????????????????????Matrix[x][y]?=?0;

????????????}
????????????for（i?=?0;?i?????????????????if（i?!=?0?&&?i?%?n?==?0）
????????????????????cout<????????????????cout<????????????}

????????????cout<????????????for（i?=?0;?i?????????????????for（j?=?0;?j?????????????????????cout<<（int）（Matrix[i][j]）<<‘?‘;
????????????????cout<????????????}
????}
????bool?Prem_Modify（int?layerint?room）{//layer當前需要移動的監控編號room可移動的上線
????????if（layer?>=?0）{
????????????for（int?i?=?layer;?i?????????????????if（CutBranch（iroomlayer））{
????????????????????Place[layer]?=?0;Place[i]?=?1;
????????????????????if（SetMonitor（layeri））return?1;//0010100000010100
????????????????????if（Prem_Modify（layer?-?1i））return?1;
????????????????????SetMonitor（ilayer）;
????????????????????Place[i]?=?0;Place[layer]?=?1;
????????????????}
????????????}
????????????return?0;
????????}
????????return?0;
????}
????bool?CutBranch（int?Range_LTint?Range_RDint?Surplus）{//剪枝
????????int?LTXLTYRDXRDY;//LT左上RD右下
????????int?ij;
????????LTX?=?Ra