当前位置：首页 -> 基础 -> c++编程基础

HDU 4770 Lights Against Dudely(枚举所有状态 当然壮压dp会很简单)(二)

2014-11-24 02:21:03 · 作者: · 浏览: 4
标签: HDU 4770 Lights Against Dudely 枚举 所有 状态 当然 简单
表示可以照亮的灯，普通的一盏灯可以照亮自己的位置和自己上和右的位置。特殊的灯可以照亮的位置可以将普通灯旋转。问你最少使用多少灯照亮所有的点。
注意：
1.每次最多有一个特殊灯。
2.总共最多是15个点。
3.一个点如果被一盏灯占住了，则不可以放灯，但是被照亮了，可以继续放灯。
解题思路：当时开始讨论的思路是暴利，时间复杂度，O（2^14*15*4）大概是10^6，然后可以加一个剪枝，top*3
题目地址：Lights Against Dudely
下面是自己的挫代码。。 
在CODE上查看代码片派生到我的代码片
#include  
#include  
#include  
using namespace std;  
int n,m,h;    //h是点的个数  
char map1[205][205];  //地图  
int dian[20][2];   //点的坐标  
int dir[4][2]= {{-1,0},{0,1},{1,0},{0,-1}}; //四个方向  
int vis[20];  
int sav[20];  
int visi[25];  //是否全部点都被照亮  
int map2[205][205];   //存放每个点的顺序  
int north[25],south[25],west[25],east[25];   //记录每个点的上下左右点的在点里的位置  
  
int ok1(int p)   //只能右上  
{  
    int x1,y1,x2,y2,x,y;  
    x=dian[p][0],y=dian[p][1];  
    x1=x+dir[0][0],y1=y+dir[0][1];  
    x2=x+dir[1][0],y2=y+dir[1][1];  
    if(map1[x1][y1]=='.'&&map1[x2][y2]=='.')  
        return 1;  
    return 0;  
}  
  
int ok2(int p,int i)   //特殊点  
{  
    int x1,y1,x2,y2,x,y,j;  
    x=dian[p][0],y=dian[p][1];  
    j=(i+1)%4;  
    x1=x+dir[i][0],y1=y+dir[i][1];  
    x2=x+dir[j][0],y2=y+dir[j][1];  
    if(map1[x1][y1]=='.'&&map1[x2][y2]=='.') return 1;  
    return 0;  
}  
  
int cover()  
{  
    int i;  
    for(i=0; i






>=1;  
            }  
  
            res=min(res,solve());  
        }  
        if(res==20) { puts("-1"); continue;}  
        else   cout<