本文主要是介绍USACO Magic Squares 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在发现8!=40320之后，我发现空间不是影响因素了。只要不重复运算，时间和空间都是足够的。
值得借鉴的地方：
1.对于转换的处理：
/* the set of transformations, in order */
static int tforms[3][8] = { {8, 7, 6, 5, 4, 3, 2, 1}, {4, 1, 2, 3, 6, 7, 8, 5},
{1, 7, 2, 4, 5, 3, 6, 8} };
这里是另外一种思路，处理起来相对更简单些。思路是直接将转化理解为对不同拷贝位置（初始位置转换后的位置）的映射。比如第一个转化里面第0为应该拷贝第7位(8-1)。第一个转化其实就是这一个数组，即拷贝位置的映射。
2.康拓展开
康拓展开是个好定理：作用是求一个排列如45213在这个5个数的全排列中的序列。可以直接移步这里：http://blog.csdn.net/fairyroad/article/details/7555773
代码写得很好。
/*
ID: thestor1
LANG: C++
TASK: msquare
*/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <stack>
#include <set>using namespace std;const int size = 8;
const int MAX = 40320;//8! = 40320
struct Square{int h;int square[size];char op;int prev;Square(){h = -1;}int hash(){if(h > 0){return h;}int h = 0;for(int i = 0; i < size; ++i){h = (h << 3) + square[i];}return h;}
};Square squares[MAX];bool equal(Square &s1, Square &s2)
{return s1.hash() == s2.hash();
}bool equal(int *s1, int *s2)
{for(int i = 0; i < size; ++i){if(s1[i] != s2[i]){return false;}}return true;
}void copy(int *s, int *d)
{for(int i = 0; i < size; ++i){d[i] = s[i];}
}void A(int *square)
{for(int i = 0; i <= 3; ++i){int tmp = square[i];square[i] = square[7 - i];square[7 - i] = tmp;}
}void B(int *square)
{int tmp = square[3];for(int i = 3; i >= 1; --i){square[i] = square[i - 1];}square[0] = tmp;tmp = square[4];for(int i = 4; i <= 6; ++i){square[i] = square[i + 1];}square[7] = tmp;
}void C(int *square)
{int tmp = square[1];square[1] = square[6];square[6] = square[5];square[5] = square[2];square[2] = tmp;
}int main()
{FILE *fin = fopen ("msquare.in", "r");FILE *fout = fopen ("msquare.out", "w");//freopen("log.txt", "w", stdout);Square targetSq;//int target[size];for(int i = 0; i < size; ++i){fscanf(fin, "%d", &targetSq.square[i]);}set<int> sqs;int top = 0;for(int i = 0; i < size; ++i){squares[top].square[i] = i + 1;}sqs.insert(squares[top].hash());top++;int final = -1;for(int i = 0; i < top; ++i){//fprintf(stdout, "i: %d, top: %d\n", i, top);Square sq = squares[i];if(equal(sq, targetSq)){final = i;break;}copy(sq.square, squares[top].square);A(squares[top].square);if(sqs.find(squares[top].hash()) == sqs.end()){squares[top].prev = i;squares[top].op = 'A';sqs.insert(squares[top].hash());top++;}copy(sq.square, squares[top].square);B(squares[top].square);if(sqs.find(squares[top].hash()) == sqs.end()){squares[top].prev = i;squares[top].op = 'B';sqs.insert(squares[top].hash());top++;}copy(sq.square, squares[top].square);C(squares[top].square);if(sqs.find(squares[top].hash()) == sqs.end()){squares[top].prev = i;squares[top].op = 'C';sqs.insert(squares[top].hash());top++;}}stack<char> seq;while(final != 0){seq.push(squares[final].op);final = squares[final].prev;}fprintf(fout, "%d\n", seq.size());while(!seq.empty()){fprintf(fout, "%c", seq.top());seq.pop();}fprintf(fout, "\n");return 0;
}这篇关于USACO Magic Squares 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
