世界名画陈列馆问题的分支限界法

#include<iostream>
#include<stdio.h>
using namespace std;

class Monitor{
    int m,n;
    char **Matrix;
    int *Place;
public:
    Monitor(){}
    Monitor(int m,int n){
        int i,j,room,x,y;
        this->m = m;
        this->n = n;

        Matrix = new char *[m];
        for(i = 0; i < m; i++)
        {
            Matrix[i] = new char [n];
        }
        room = m * n;
        Place = new int [room];
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                Matrix[i][j] = 0;
            }
        }

        i = room / 5;
        if(room % 5) i++;
        for(; i < room; i++)
        {
            for(j = 0; j < i; Place[j++] = 1) SetMonitor(-4,j);
            while(j < room)   Place[j++] = 0;
            if(Prem_Modify(i - 1,room)) break;
            for(x = 0; x < m; x++)
            {
                for(y = 0; y < n; y++)
                {
                    Matrix[x][y] = 0;
                }
            }

        }
        for(i = 0; i < room; i++)
        {
            if(i != 0 && i % n == 0) printf("\n");
            printf("%d",Place[i]);
        }
    }
    bool Prem_Modify(int Layer,int room)
    {
        if(Layer >= 0)
        {
            for(int i = Layer; i < room; i++)
            {
                if(CutBranch(i,room,Layer))
                {
                    Place[Layer] = 0;
                    Place[i] = 1;
                    if(SetMonitor(Layer,i))     return 1;
                    if(Prem_Modify(Layer - 1,i))return 1;
                    SetMonitor(i,Layer);
                    Place[i] = 0;
                    Place[Layer] = 1;
                }
            }
            return 0;
        }
        return 0;
    }
    bool CutBranch(int Range_LT,int Range_RD,int Surplus)
    {
        int LTX,LTY,RDX,RDY;
        int i,j;
        LTX = Range_LT / n + 1;
        LTY = Range_LT % n + 1;
        if(Range_RD == m * n){RDX = m - 1;RDY = n - 1;}
        else{RDX = Range_RD / n - 1;RDY = Range_RD % n - 1;}

        for(i = LTX + 1; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                if(Matrix[i][j] == 0) return 0;
            }
        }
        for(i = LTX ; i <= RDX; i++)
        {
            for(j = LTY; j <= RDY; j++)
            {
                if(i < m && j < n && Matrix[i][j] == 0)  return 0;
            }
        }
        if((Surplus + 1) * 5 < Range_LT)    return 0;
        return 1;
    }
    bool SetMonitor(int Demolition,int Set)
    {
        int DemolitionX,DemolitionY,SetX,SetY;
        int i,j;

        DemolitionX = Demolition / n;
        DemolitionY = Demolition % n;
        SetX = Set / n;
        SetY = Set % n;

        Matrix[SetX][SetY]++;
        if(Demolition >= 0)
        {
            Matrix[DemolitionX][DemolitionY]--;
            if(DemolitionX - 1 >= 0)
                Matrix[DemolitionX - 1][DemolitionY]--;
            if(DemolitionX + 1 < n)
                Matrix[DemolitionX + 1][DemolitionY]--;
            if(DemolitionY - 1 >= 0)
                Matrix[DemolitionX ][DemolitionY- 1]--;
            if(DemolitionY + 1 < m)
                Matrix[DemolitionX ][DemolitionY+ 1]--;
        }
        if(SetX - 1 >= 0)
            Matrix[SetX - 1][SetY]++;
        if(SetX + 1 < n)
            Matrix[SetX+ 1][SetY]++;
        if(SetY - 1 >= 0)
            Matrix[SetX][SetY- 1]++;
        if(SetY + 1 < m)
            Matrix[SetX][SetY+ 1]++;

        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                if(Matrix[i][j] == 0)   return 0;
            }
        }
        return 1;
    }
    ~Monitor(){
        for(int i = 0; i < m; i++)
        {
            delete Matrix[i];
        }
        delete Matrix;
    }
};
int main()
{
    int row,col;
    printf("请输入行和列:");
    scanf("%d%d",&row,&col);
    printf("机器人的排列方式为:\n");
    class Monitor  M(row,col);
    return 1;
}
0

Leave a Reply

Your email address will not be published.