POJ 1166解题报告
阅读量：4205 次
发布时间：2019-05-26
本文共 5073 字，大约阅读时间需要 16 分钟。
这道题首先是从USACO上看到的，然后用特别标准的BFS（队列+set）从初始状态到目标状态（全是0）转换。刚开始用一个int表示一个状态，用一个10^9的bool数组记录是否被访问过，结果超出了空间。改成map<int>记录后时间超了。权衡之下多加了个hash，因为每位只能取0~3（分别代表12，3，6，9），所以只需要4^9空间。这样就通过了usaco的测试。
代码如下：
#include #include #include #include #include #include #include #include using namespace std;const int numrules = 9;const int numclocks = 9;bool visited[262144];int base[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};struct State{ int state; vector ops; State() { } State(int state, vector ops) { this->state = state; this->ops = ops; }};int move(int state, int rule[]){ int newstate = state; for(int i = 0; i < 6 && rule[i] != -1; ++i) { int bit = (state / base[rule[i]]) % 10; newstate = newstate - bit * base[rule[i]] + ((bit + 1) % 4) * base[rule[i]]; } return newstate;}int fhash(int state){ int i = 0; int h = 0; while(state != 0) { h += (state % 10) << i; i += 2; state /= 10; } return h;}int main(){ //FILE *fin, *fout; //fin = fopen("clocks.in", "r"); //fout = fopen("clocks.out", "w"); //assert(fin != NULL && fout != NULL); int rules[numrules][6] = { {0, 1, 3, 4, -1}, {0, 1, 2, -1}, {1, 2, 4, 5, -1}, {0, 3, 6, -1}, {1, 3, 4, 5, 7, -1}, {2, 5, 8, -1}, {3, 4, 6, 7, -1}, {6, 7, 8, -1}, {4, 5, 7, 8, -1}}; int initstate = 0; int hour; int base = 1; for(int i = 0; i < 9; ++i) { //fscanf(fin, "%d", &hour); fscanf(stdin, "%d", &hour); initstate += hour * base; //initstate += ((hour / 3) % 4) * base; base *= 10; } //set visited; memset(visited, false, 262144 * sizeof(bool)); queue que; que.push(State(initstate, vector ())); visited[fhash(initstate)] = true; //visited.insert(initstate); const int finalstate = 0; int cur = 1; int next = 0; State state; int nummove = 0; while(!que.empty()) { state = que.front(); que.pop(); cur--; if(state.state == finalstate) { //cout< <
ops = state.ops; ops.push_back(i); que.push(State(newstate, ops)); //visited.insert(newstate); visited[fhash(newstate)] = true; next++; } } if(cur == 0) { cur = next; next = 0; nummove++; } } return 0;}
后来看到POJ1166是同一道题，事实证明POJ的测试标准要高很多，上述解法TLE了。
于是用了另外一种方法。
因为每种move只能执行0~3次（执行4次就和没变一样了），而且操作之间的先后次序不会影响结果（先拨后拨钟而已），所以按照题目的输出要求只用9个循环把9个move从0~3试一下就可以。
意思很简单，代码相当难看。
代码如下：
#include #include #include #include #include #include #include #include using namespace std;const int numrules = 9;const int numclocks = 9;void apply(int *initstate, int *newstate, int *rules0, int rep0, int *rules1, int rep1, int *rules2, int rep2, int *rules3, int rep3, int *rules4, int rep4, int *rules5, int rep5, int *rules6, int rep6, int *rules7, int rep7, int *rules8, int rep8){ for(int i = 0; i < numclocks; ++i) { newstate[i] = initstate[i]; } for(int i = 0; i < numclocks && rules0[i] != -1; ++i) { newstate[rules0[i]] = (newstate[rules0[i]] + rep0) % 4; } for(int i = 0; i < numclocks && rules1[i] != -1; ++i) { newstate[rules1[i]] = (newstate[rules1[i]] + rep1) % 4; } for(int i = 0; i < numclocks && rules2[i] != -1; ++i) { newstate[rules2[i]] = (newstate[rules2[i]] + rep2) % 4; } for(int i = 0; i < numclocks && rules3[i] != -1; ++i) { newstate[rules3[i]] = (newstate[rules3[i]] + rep3) % 4; } for(int i = 0; i < numclocks && rules4[i] != -1; ++i) { newstate[rules4[i]] = (newstate[rules4[i]] + rep4) % 4; } for(int i = 0; i < numclocks && rules5[i] != -1; ++i) { newstate[rules5[i]] = (newstate[rules5[i]] + rep5) % 4; } for(int i = 0; i < numclocks && rules6[i] != -1; ++i) { newstate[rules6[i]] = (newstate[rules6[i]] + rep6) % 4; } for(int i = 0; i < numclocks && rules7[i] != -1; ++i) { newstate[rules7[i]] = (newstate[rules7[i]] + rep7) % 4; } for(int i = 0; i < numclocks && rules8[i] != -1; ++i) { newstate[rules8[i]] = (newstate[rules8[i]] + rep8) % 4; }}bool check(int *state){ for(int i = 0; i < numclocks; ++i) { if(state[i]) return false; } return true;}void print(int rep0, int rep1, int rep2, int rep3, int rep4, int rep5, int rep6, int rep7, int rep8){ for(int i = 0; i < rep0; ++i) { cout<<"1 "; } for(int i = 0; i < rep1; ++i) { cout<<"2 "; } for(int i = 0; i < rep2; ++i) { cout<<"3 "; } for(int i = 0; i < rep3; ++i) { cout<<"4 "; } for(int i = 0; i < rep4; ++i) { cout<<"5 "; } for(int i = 0; i < rep5; ++i) { cout<<"6 "; } for(int i = 0; i < rep6; ++i) { cout<<"7 "; } for(int i = 0; i < rep7; ++i) { cout<<"8 "; } for(int i = 0; i < rep8; ++i) { cout<<"9 "; } cout< >initstate[i]; } int newstate[numclocks]; for(int rep0 = 0; rep0 < 4; ++rep0) for(int rep1 = 0; rep1 < 4; ++rep1) for(int rep2 = 0; rep2 < 4; ++rep2) for(int rep3 = 0; rep3 < 4; ++rep3) for(int rep4 = 0; rep4 < 4; ++rep4) for(int rep5 = 0; rep5 < 4; ++rep5) for(int rep6 = 0; rep6 < 4; ++rep6) for(int rep7 = 0; rep7 < 4; ++rep7) for(int rep8 = 0; rep8 < 4; ++rep8) { apply(initstate, newstate, rules[0], rep0, rules[1], rep1, rules[2], rep2, rules[3], rep3, rules[4], rep4, rules[5], rep5, rules[6], rep6, rules[7], rep7, rules[8], rep8); if(check(newstate)) { print(rep0, rep1, rep2, rep3, rep4, rep5, rep6, rep7, rep8); return 0; } } return 0;}
转载地址：http://xxxli.baihongyu.com/