程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> icpc live archive6454(狀壓搜索)

icpc live archive6454(狀壓搜索)

編輯：C++入門知識

icpc live archive6454(狀壓搜索)

https://icpcarchive.ecs.baylor.edu/external/64/6454.pdf

求最少的燈照亮所有.的區域，但不能照到#號區域，可以照到界限之外，每個.號上只能放一盞燈。燈照的區域為L形，燈在拐角處。大多數燈是這樣沒錯，但有一盞燈比較特殊，可以是L的其他三種旋轉體。

狀態壓縮搜索，狀態為放置的燈的狀態，（.）點最多只有15個，做好序號可以直接存進一個int型裡。

代碼（中間有一些比較繁瑣）：

#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define MOD 100000007
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=202;
char g[maxn][maxn];
int opp[maxn][maxn];
bool done[100000];
int n,m,k,cnt,sx,sy,point;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int aimx[20],aimy[20];
struct node
{
    int w,key,stat,no;//w為走的步數，key為可以放燈的點狀態，stat為燈照亮的區域（一定是15個點中的嘛），no為還有幾個特殊燈沒放。
    node(int ww=0,int k=0,int st=0,int n=0)
    {
        w=ww;key=k;stat=st;no=n;
    }
};
bool is_ill(int x,int y)
{
    return x<0||x>=n||y<0||y>=m;
}

int bfs()
{
    queueq;
    memset(done,0,sizeof done);
    q.push(node(0,k,k,1));
    done[k]=1;
    while(!q.empty())
    {
        node e=q.front();q.pop();
        for(int i=0;i