Posted on 2007-06-29 22:29
ZelluX 阅读(268)
评论(0) 编辑 收藏 所属分类:
Algorithm
wrong answer了几次，总算过了
gdb还是不怎么会用，调试dfs时不知道怎么跳出当前层(finish和up貌似都不管用)，以及如何step over
/*
PROG: lamps
ID: 06301031
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct StateArray
{
bool value[100];
};
int n, c;
int methodCount = 0;
vector<int> reqOn, reqOff;
vector<StateArray> result;
int method[4];
bool state[100]; // On - true, Off - false
bool equalState(const StateArray& s1, const StateArray& s2)
{
for (int i = 0; i < n; i++)
if (s1.value[i] != s2.value[i])
return false;
return true;
}
bool compareState(const StateArray& s1, const StateArray& s2)
{
for (int i = 0; i < n; i++)
if (s1.value[i] != s2.value[i])
return !s1.value[i];
return false;
}
void changeState(int m) // m[0,4] refers to the method
{
switch (m)
{
case 0:
for (int i = 0; i < n; i++)
state[i] = !state[i];
break;
case 1:
for (int i = 0; i < n; i += 2)
state[i] = !state[i];
break;
case 2:
for (int i = 1; i < n; i += 2)
state[i] = !state[i];
break;
case 3:
for (int i = 0; i < n; i += 3)
state[i] = !state[i];
break;
}
}
bool validState()
{
for (int i = 0; i < reqOn.size(); i++)
if (!state[reqOn[i]])
return false;
for (int i = 0; i < reqOff.size(); i++)
if (state[reqOff[i]])
return false;
return true;
}
void DFS(int t) // t: method number
{
if ((methodCount > c) || (t >= 4))
return;
for (int i = 0; i < 2; i++)
{
if (i == 1)
{
methodCount++;
changeState(t);
if (((c - methodCount) % 2 == 0) && validState())
{
StateArray tempState;
for (int j = 0; j < n; j++)
{
tempState.value[j] = state[j];
}
result.push_back(tempState);
}
DFS(t + 1);
methodCount--;
changeState(t);
}
else
{
if (((c - methodCount) % 2 == 0) && validState())
{
StateArray tempState;
for (int j = 0; j < n; j++)
{
tempState.value[j] = state[j];
}
result.push_back(tempState);
}
DFS(t + 1);
}
}
}
int main()
{
ifstream fin("lamps.in");
ofstream fout("lamps.out");
fin >> n >> c;
int x;
while (fin >> x)
if (x == -1)
break;
else
reqOn.push_back(x - 1);
while (fin >> x)
if (x == -1)
break;
else
reqOff.push_back(x - 1);
for (int i = 0; i < n; i++)
state[i] = true;
DFS(0);
if (result.size() < 1)
fout << "IMPOSSIBLE\n";
sort(result.begin(), result.end(), compareState);
vector<StateArray>::iterator iter;
vector<StateArray> uni;
for (iter = result.begin(); iter != result.end(); iter++)
if (uni.empty() || !equalState(uni[uni.size() - 1], *iter))
uni.push_back(*iter);
for (int i = 0; i < uni.size(); i++)
{
for (int j = 0; j < n; j++)
{
fout << uni[i].value[j];
}
fout << endl;
}
return 0;
}