DFS解決任意組合問(wèn)題
描述
在IOI98的節(jié)日宴會(huì)上，我們有N(10<=N<=100)盞彩色燈，他們分別從1到N被標(biāo)上號(hào)碼。 這些燈都連接到四個(gè)按鈕：
按鈕1：當(dāng)按下此按鈕，將改變所有的燈：本來(lái)亮著的燈就熄滅，本來(lái)是關(guān)著的燈被點(diǎn)亮。
按鈕2：當(dāng)按下此按鈕，將改變所有奇數(shù)號(hào)的燈。
按鈕3：當(dāng)按下此按鈕，將改變所有偶數(shù)號(hào)的燈。
按鈕4：當(dāng)按下此按鈕，將改變所有序號(hào)是3*K+1(K>=0)的燈。例如：1,4,7...
一個(gè)計(jì)數(shù)器C記錄按鈕被按下的次數(shù)。當(dāng)宴會(huì)開(kāi)始，所有的燈都亮著，此時(shí)計(jì)數(shù)器C為0。
你將得到計(jì)數(shù)器C(0<=C<=10000)上的數(shù)值和經(jīng)過(guò)若干操作后某些燈的狀態(tài)。寫(xiě)一個(gè)程序去找出所有燈最后可能的與所給出信息相符的狀態(tài)，并且沒(méi)有重復(fù)。
格式
PROGRAM NAME: lamps
INPUT FORMAT:
(file lamps.in)
不會(huì)有燈會(huì)在輸入中出現(xiàn)兩次。
第一行: N。
第二行: C最后顯示的數(shù)值。
第三行: 最后亮著的燈,用一個(gè)空格分開(kāi)，以-1為結(jié)束。
第四行: 最后關(guān)著的燈,用一個(gè)空格分開(kāi)，以-1為結(jié)束。
OUTPUT FORMAT:
(file lamps.out)
每一行是所有燈可能的最后狀態(tài)(沒(méi)有重復(fù))。每一行有N個(gè)字符，第1個(gè)字符表示1號(hào)燈，最后一個(gè)字符表示N號(hào)燈。0表示關(guān)閉，1表示亮著。這些行必須從小到大排列（看作是二進(jìn)制數(shù)）。
如果沒(méi)有可能的狀態(tài)，則輸出一行'IMPOSSIBLE'。
SAMPLE INPUT
10 //一共有10盞燈
1 //按鈕的操作次數(shù)
-1 //on，以-1結(jié)束
7 -1 //off,以-1結(jié)束
在這個(gè)樣例中，有10盞燈，只有1個(gè)按鈕被按下。最后7號(hào)燈是關(guān)著的。
SAMPLE OUTPUT
0000000000
0101010101
0110110110
在這個(gè)樣例中，有三種可能的狀態(tài)：
所有燈都關(guān)著
1,4,7,10號(hào)燈關(guān)著，2,3,5,6,8,9亮著。
1,3,5,7,9號(hào)燈關(guān)著，2, 4, 6, 8, 10亮著。
注意：這里一共有4種操作，那這里所說(shuō)的任意組合就是這四種操作之間的任意組合。要搞清楚。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
string s[102];
bool off[102],on[102],ans[102],v[5];
int n,c,sum;
bool cmp(string x,string y)
{
return x<y;
}
char find(bool f)
{
if (f) return '1';
return '0';
}
void check()
{
int k=0;
for (int i=1; i<=n; ++i)
{
if (on[i]&&!ans[i]) return; //標(biāo)準(zhǔn)為開(kāi)，而ans為！開(kāi)，不行
if (off[i]&&ans[i]) return; //標(biāo)準(zhǔn)為關(guān)，而ans為關(guān)，不行
}
for (int i=1; i<=4; ++i)
if (v[i]) k++; //v[i]可行,k記錄四種開(kāi)關(guān)的操作次數(shù)，不能大于C
if (k>c) return;
if ((c-k)%2!=0) return;
//查找成功，統(tǒng)計(jì)結(jié)果
for (int i=1; i<=n; ++i)
s[sum]=s[sum]+find(ans[i]);
sum++;
}
void dfs(int x)
{
if (x>4)
{
check();
return;
}
dfs(x+1); //如果搜索了。
v[x]=true;
if (x==1) //開(kāi)關(guān)1的操作
for (int i=1; i<=n; i+=1)
ans[i]=!ans[i];
if (x==2) //開(kāi)關(guān)2的操作
for (int i=1; i<=n; i+=2)
ans[i]=!ans[i];
if (x==3) //開(kāi)關(guān)3的操作
for (int i=0; i<=n; i+=2)
ans[i]=!ans[i];
if (x==4) //開(kāi)關(guān)4的操作
for (int i=0; i<=n/3; i++)
ans[i*3+1]=!ans[i*3+1];
dfs(x+1); //還原剛才搜索的東西，為了下次的搜索
v[x]=false;
if (x==1) //開(kāi)關(guān)1的操作
for (int i=1; i<=n; i+=1)
ans[i]=!ans[i];
if (x==2) //開(kāi)關(guān)2的操作
for (int i=1; i<=n; i+=2)
ans[i]=!ans[i];
if (x==3) //開(kāi)關(guān)3的操作
for (int i=0; i<=n; i+=2)
ans[i]=!ans[i];
if (x==4) //開(kāi)關(guān)4的操作
for (int i=0; i<=n/3; i++)
ans[i*3+1]=!ans[i*3+1];
}
int main()
{
cin>>n>>c;
int k;
sum=0;
memset(v,0,sizeof(v));
memset(on,0,sizeof(on));
memset(ans,1,sizeof(ans));
memset(off,0,sizeof(off));
while(cin>>k && k!=-1) on[k]=true;
while(cin>>k && k!=-1) off[k]=true;
dfs(1);
sort(s,s+sum,cmp);
for (int i=0; i<sum; ++i) cout<<s[i]<<endl;
if (sum==0) cout<<"IMPOSSIBLE"<<endl;
return 0;
}
posted on 2011-10-24 23:02 More study needed. 閱讀(402) 評(píng)論(0) 收藏 舉報(bào)
浙公網(wǎng)安備 33010602011771號(hào)