[USACO][Section 2.2][枚举] Party Lamps

题目大意：

给出一排灯，4个按钮，每个按钮可以使特定位置的灯改变状态。规定操作数c和目标状态，输出c次操作后所有符合目标状态的状态。

思路：

利用深搜按操作次数枚举4^c个状态。

代码：

/*
ID: lujunda1
LANG: C++
PROG: lamps
*/
#include
#include
#include
#include
using namespace std;
int n,c,total;
bool on[102],off[102];
//on[]、off[]用于记录目标状态。 
map mark;
//对状态进行标记，避免重复搜索。 
struct point 
//对用结构体对状态进行封装，便于利用qsort排序。
{
    char arry[102];
}res[16]; 
int cmp(const void* m,const void* n)
//qsort的排序函数。 
{
    return strcmp((*(point*)m).arry+1,(*(point*)n).arry+1);
    //注意下标是从1开始的，而不是0。 
}
void input()
//输入 
{
    scanf("%d%d",&n,&c);
    if(c>4)
        c=c%2?3:4;
        //注意对C的处理，当c>4时，必然会出现同一按钮按多次的情况。 
    for(int i=0;i<102;i++)
        on[i]=off[i]=false;
    int t;
    while(~scanf("%d",&t)&&t!=-1)
        on[t]=true;
    while(~scanf("%d",&t)&&t!=-1)
        off[t]=true;
}
void output()
//输出 
{
    if(!total)
    {
        printf("IMPOSSIBLE\n");
        return;
    }
    qsort(res,total,sizeof(res[0]),cmp);
    for(int i=0;i<total;i++)
        printf("%s\n",res[i].arry+1);
}
point op(int t,point temp)
//operation操作函数。
//参数t表示按钮编号。
//temp表示按钮作用的对象状态。 
{
    if(t==1)
        for(int i=1;i<=n;i++)
            temp.arry[i]=temp.arry[i]-'0'?'0':'1';
    else if(t==2)
        for(int i=1;i<=n;i+=2)
            temp.arry[i]=temp.arry[i]-'0'?'0':'1';
    else if(t==3)
        for(int i=2;i<=n;i+=2)
            temp.arry[i]=temp.arry[i]-'0'?'0':'1';
    else
        for(int i=0;3*i+1<=n;i++)
            temp.arry[3*i+1]=temp.arry[3*i+1]-'0'?'0':'1';
    return temp;
}
bool check(point temp)
//检查temp是否与目标状态相符。 
{
    for(int i=1;i<=n;i++)
    {
        if(on[i]&&temp.arry[i]=='0')
            return false;
        if(off[i]&&temp.arry[i]=='1')
            return false;
    }
    string result=temp.arry;
    if(mark[result])
    //检查temp是否与其他已确定的状态相重复。 
        return false;
    mark[result]=true;
    return true;
}
void dfs(point temp,int sum)
//利用深搜枚举4^c种状态。 
{
    if(sum==c)
    {
        if(check(temp))
            res[total++]=temp;
        return;
    }
    for(int i=1;i<5;i++)
        dfs(op(i,temp),sum+1);
}
int main()
{
    freopen("lamps.in","r",stdin);
    freopen("lamps.out","w",stdout);
    input();
    total=0;
    //符合目标状态的状态的总数。初始化为0。 
    point temp;
    for(int i=1;i<=n;i++)
        temp.arry[i]='1';
    temp.arry[n+1]='\0';
    dfs(temp,0);
    output();
}

发表回复取消回复