|
|
Posted on 2007-05-30 21:34 ZelluX 阅读(762) 评论(0) 编辑 收藏 所属分类: Algorithm
本来想练习了下deque的使用。用BFS，每个结点都记录了到目前为止转动的情况。结果发现内存消耗很大，就只好用DFS了。
  /**//*
 PROG: clocks
ID: 06301031
LANG: C++
 */
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
// A B C D E F G H I
// 0 1 2 3 4 5 6 7 8
const int moves[9][5] =  {{0,1,3,4,-1}, {0,1,2,-1,-1}, {1,2,4,5,-1}, {0,3,6,-1,-1},
  {1,3,4,5,7}, {2,5,8,-1,-1}, {3,4,6,7,-1}, {6,7,8,-1,-1}, {4,5,7,8,-1}};
static int minMoves = 50;
static int bestSolution[9];
void DFS(int status[], int method[], int t, int count) {
int i, j;
if (count > minMoves) {
return;
 }
bool flag = true;
for (i = 0; i < 9; i++) {
if (status[i] != 12) {
flag = false;
break;
}
}
if (flag) {
if (count == minMoves) {
for (i = 0; i < 9; i++) {
if (bestSolution[i] > method[i]) {
return;
}
if (bestSolution[i] < method[i]) {
break;
}
}
}
minMoves = count;
for (int i = 0; i < 9; i++) {
bestSolution[i] = method[i];
}
return;
}
if (t >= 9) {
return;
}
for (i = 0; i < 4; i++) {
method[t] = i;
if (i == 0) {
DFS(status, method, t + 1, count);
continue;
}
// i != 0
for (j = 0; j < 5; j++) {
if (moves[t][j] < 0) {
break;
}
status[moves[t][j]] += 3;
if (status[moves[t][j]] > 12) {
status[moves[t][j]] = 3;
}
}
DFS(status, method, t + 1, count + i);
}
// Turn the status again, to change it back.
for (j = 0; j < 5; j++) {
if (moves[t][j] < 0) {
break;
}
status[moves[t][j]] += 3;
if (status[moves[t][j]] > 12) {
status[moves[t][j]] = 3;
}
}
method[t] = 0;
}
int main() {
ifstream fin("clocks.in");
ofstream fout("clocks.out");
int start[9], method[9];
int i, j;
for (i = 0; i < 9; i++) {
fin >> start[i];
}
for (i = 0; i < 9; i++) {
method[i] = 0;
}
for (i = 0; i < 9; i++) {
bestSolution[i] = 4;
}
DFS(start, method, 0, 0);
vector<int> answer;
for (i = 0; i < 9; i++) {
if (bestSolution[i] > 0) {
for (j = 0; j < bestSolution[i]; j++) {
answer.push_back(i + 1);
}
}
}
fout << answer[0];
for (i = 1; i < answer.size(); i++) {
fout << " " << answer[i];
}
fout << endl;
fout.close();
return 0;
}
|