回 帖 发 新 帖 刷新版面

主题:世界名画陈列馆问题

用C或者C++做世界名画陈列馆问题
1.问题描述
世界名画陈列馆有m*n个陈列室组成。为了防止名画被盗,需要在陈列室设置警卫机器人哨位,每算法个警卫机器人除了监视它所在的陈列室之外,还可以监视与它所在的陈列室相邻的上,下,左,右4个陈列室。
2.要求
试要求,设计一个安排警卫机器人哨位的算法,使得名画陈列馆的每个陈列室都在警卫机器人监视之下,切所用的警卫机器人数目最少。

用分枝限界法做,怎么做?高人指点。

回复列表 (共1个回复)

沙发

#include <fstream>
using namespace std;
ifstream fin ("rob.in");
ofstream fout("rob.out");
main ()
{
     int n,m,k;
     fin>>n>>m;
     if(n>m)
     {
            k=n;
            n=m;
            m=k;
     }
     if(n==1)
     if(m%3==0)k=m/3;
     else 
     k=m/3+1;
     else
     if(n==2)
     {
             if(m%2==1)k=(m-3)/2+2;
             else 
            {
                  fout<<"No Solution!";k=0;
            }
     }
     else
     if(n==3)
     {
                   fout<<"No Solution!";k=0;
     }
     else
     if(n==4&&m==4)
     k=4;
     else
     if(n>=3&&m>=5)
     {
                    fout<<"No Solution!";k=0;
     }
     if (k!=0)
     fout << k;
}



我来回复

您尚未登录,请登录后再回复。点此登录或注册