首页 > 代码库 > hdu 4770 Lights Against Dudely

hdu 4770 Lights Against Dudely

2024-07-07 05:52:27   223人阅读

Problem Description
Harry: "But Hagrid. How am I going to pay for all of this? I haven‘t any money." 
Hagrid: "Well there‘s your money, Harry! Gringotts, the wizard bank! Ain‘t no safer place. Not one. Except perhaps Hogwarts." 
— Rubeus Hagrid to Harry Potter. 
  Gringotts Wizarding Bank is the only bank of the wizarding world, and is owned and operated by goblins. It was created by a goblin called Gringott. Its main offices are located in the North Side of Diagon Alley in London, England. In addition to storing money and valuables for wizards and witches, one can go there to exchange Muggle money for wizarding money. The currency exchanged by Muggles is later returned to circulation in the Muggle world by goblins. According to Rubeus Hagrid, other than Hogwarts School of Witchcraft and Wizardry, Gringotts is the safest place in the wizarding world.
  The text above is quoted from Harry Potter Wiki. But now Gringotts Wizarding Bank is not safe anymore. The stupid Dudley, Harry Potter‘s cousin, just robbed the bank. Of course, uncle Vernon, the drill seller, is behind the curtain because he has the most advanced drills in the world. Dudley drove an invisible and soundless drilling machine into the bank, and stole all Harry Potter‘s wizarding money and Muggle money. Dumbledore couldn‘t stand with it. He ordered to put some magic lights in the bank rooms to detect Dudley‘s drilling machine. The bank can be considered as a N × M grid consisting of N × M rooms. Each room has a coordinate. The coordinates of the upper-left room is (1,1) , the down-right room is (N,M) and the room below the upper-left room is (2,1)..... A 3×4 bank grid is shown below:

　　Some rooms are indestructible and some rooms are vulnerable. Dudely‘s machine can only pass the vulnerable rooms. So lights must be put to light up all vulnerable rooms. There are at most fifteen vulnerable rooms in the bank. You can at most put one light in one room. The light of the lights can penetrate the walls. If you put a light in room (x,y), it lights up three rooms: room (x,y), room (x-1,y) and room (x,y+1). Dumbledore has only one special light whose lighting direction can be turned by 0 degree,90 degrees, 180 degrees or 270 degrees. For example, if the special light is put in room (x,y) and its lighting direction is turned by 90 degrees, it will light up room (x,y), room (x,y+1 ) and room (x+1,y). Now please help Dumbledore to figure out at least how many lights he has to use to light up all vulnerable rooms.
　　Please pay attention that you can‘t light up any indestructible rooms, because the goblins there hate light. 

 

Input
　　There are several test cases.
　　In each test case:
　　The first line are two integers N and M, meaning that the bank is a N × M grid(0<N,M <= 200).
　　Then a N×M matrix follows. Each element is a letter standing for a room. ‘#‘ means a indestructible room, and ‘.‘ means a vulnerable room. 
　　The input ends with N = 0 and M = 0
 

Output
　　For each test case, print the minimum number of lights which Dumbledore needs to put.
　　If there are no vulnerable rooms, print 0.
　　If Dumbledore has no way to light up all vulnerable rooms, print -1.
 

Sample Input
2 2
##
##
2 3
#..
..#
3 3
###
#.#
###
0 0
 

Sample Output
0
2
-1
 

题目：给出一个银行的房间的地图，每个房间占一个格子，房间分为坚固的房间和脆弱的房间。现在需要使用灯照亮那些脆弱的房间，这些灯可以穿透房间，假设在（x，y）放有一盏灯，那么它可以照亮（x，y）（x-1，y）（x，y+1），主人有一盏特殊的灯，它照亮的方向可以旋转90，180，270度，问是否能够使用这些灯照亮所有脆弱的房间（不能照亮任意一间坚固的房间）。


方法：一开始的思路 是要使用搜索来解决的，但是写到一半写不下去了。然后 看了大神的思路，觉得很好，就按照他的思路写了 一下。具体思路就是 因为脆弱的房间的个数不超过15，那么我们可以直接就二进制暴力枚举就可以了。最多的策略数就是2^15个，然后就是需要旋转的房间单独处理就可以了，这样的复杂度是可以接受的。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF  1000
using namespace std;
char ma[202][202];
int vis[20];
struct node    //用来记录每个脆弱的房间的坐标
{
    int x,y;
} nd[20];
struct dir    //记录可以旋转的灯可以照亮的房间的坐标方向
{
    int x[3];
    int y[3];
} d[4];
void init()  //四个旋转的方向的初始化
{
    d[0].x[0]=0;
    d[0].y[0]=0;
    d[0].x[1]=-1;
    d[0].y[1]=0;
    d[0].x[2]=0;
    d[0].y[2]=1;

    d[1].x[0]=0;
    d[1].y[0]=0;
    d[1].x[1]=-1;
    d[1].y[1]=0;
    d[1].x[2]=0;
    d[1].y[2]=-1;

    d[2].x[0]=0;
    d[2].y[0]=0;
    d[2].x[1]=0;
    d[2].y[1]=-1;
    d[2].x[2]=1;
    d[2].y[2]=0;

    d[3].x[0]=0;
    d[3].y[0]=0;
    d[3].x[1]=1;
    d[3].y[1]=0;
    d[3].x[2]=0;
    d[3].y[2]=1;
}

int main()
{
    int n,m,k;
    init();
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        k=0;      //k用来记录所有的脆弱的房间的个数
        for(int i=1; i<=n; i++)
        {
            scanf("%s",&ma[i][1]);
            for(int j=1; j<=m; j++)
                if(ma[i][j]=='.')
                {
                    ma[i][j]=k;        //直接把地图的点标记成记录的第K个点，后续处理会简单许多
                    nd[k].x=i;
                    nd[k++].y=j;
                }
        }

        if(k==0)
        {
            printf("0\n");
            continue;
        }
        int x,y,ans=INF,tx,ty;
        int num=(1<<k);
        bool flag=true;
        for(int i=1; i<num; i++)      //二进制枚举
        {
            for(int j=0; j<k; j++)   //枚举第j位可旋转
                if(i&(1<<j))
                {
                    memset(vis,0,sizeof(vis));
                    flag=true;
                    for(int mm=0; mm<k&&flag; mm++) //枚举其他位的情况
                        if(i&(1<<mm)&&j!=mm)
                        {
                            x=nd[mm].x;
                            y=nd[mm].y;
                            vis[ma[x][y]]=1;
                            if(x>=2)
                            {
                                if(ma[x-1][y]!='#')
                                    vis[ma[x-1][y]]=1;
                                else flag=false;
                            }
                            if(y+1<=m)
                            {
                                if(ma[x][y+1]!='#')
                                    vis[ma[x][y+1]]=1;
                                else flag=false;
                            }
                        }
                    if(!flag) continue;
                    for(int nn=0; nn<=3; nn++)   //枚举可旋转房间的四个方向
                    {
                        flag=true;
                        tx=-1;
                        ty=-1;
                        x=nd[j].x+d[nn].x[1];
                        y=nd[j].y+d[nn].y[1];
                        if(x>=1&&x<=n&&y>=1&&y<=m)
                        {
                            if(ma[x][y]!='#')
                                tx=ma[x][y];     //因为四个方向总要改变vis比较麻烦，所以单独处理旋转的房间覆盖的房间
                            else flag=false;
                        }
                        x=nd[j].x+d[nn].x[2];
                        y=nd[j].y+d[nn].y[2];
                        if(x>=1&&x<=n&&y>=1&&y<=m)
                        {
                            if(ma[x][y]!='#')
                                ty=ma[x][y];    //同上
                            else flag=false;
                        }
                        vis[j]=1;               //别忘了这一步
                        if(flag)
                        {
                            int sum=0;
                            for(int v=0; v<k; v++)
                                if(!vis[v]&&tx!=v&&ty!=v)    //枚举所有的房间，看是否的房间都已经被覆盖
                                {
                                    flag=false;
                                    break;
                                }
                            if(flag)
                            {
                                for(int v=0; v<k; v++)
                                    if(i&(1<<v)) sum++;
                                if(ans>sum) ans=sum;
                            }
                        }
                    }
                }
        }
        if(ans<INF) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}







联系
我们