//放在USACO上一直通不过 不知道哪里出了问题 输出的n总是等于1 但是BFS递归的次数是对的 《----这个问题解决了 局部变量压入queue中返回就是对的了
#include<iostream>
#include <fstream>
#include<cstring>
#include<queue>
using namespace std;
typedef struct
{
int clock[9]; //当前状态
int sq[100]; //已扩展序号
int n; //已扩展次数
}CS;
int clockadd(int* c)
{
int t = *c;
if(t == 12)
t = 3;
else
t = t + 3;
*c = t;
return 0;
}
int Move(int m, int *clock)
{
switch(m)
{
case 1:
{
clockadd(&clock[0]); clockadd(&clock[1]); clockadd(&clock[3]); clockadd(&clock[4]);
}
break;
case 2:
{
clockadd(&clock[0]); clockadd(&clock[1]); clockadd(&clock[2]);
}
break;
case 3:
{
clockadd(&clock[1]); clockadd(&clock[2]); clockadd(&clock[4]); clockadd(&clock[5]);
}
break;
case 4:
{
clockadd(&clock[0]); clockadd(&clock[3]); clockadd(&clock[6]);
}
break;
case 5:
{
clockadd(&clock[1]); clockadd(&clock[3]); clockadd(&clock[4]); clockadd(&clock[5]); clockadd(&clock[7]);
}
break;
case 6:
{
clockadd(&clock[2]); clockadd(&clock[5]); clockadd(&clock[8]);
}
break;
case 7:
{
clockadd(&clock[3]); clockadd(&clock[4]); clockadd(&clock[6]); clockadd(&clock[7]);
}
break;
case 8:
{
clockadd(&clock[6]); clockadd(&clock[7]); clockadd(&clock[8]);
}
break;
case 9:
{
clockadd(&clock[4]); clockadd(&clock[5]); clockadd(&clock[7]); clockadd(&clock[8]);
}
break;
default:
break;
}
return 0;
}
int clockok(int * clock)
{
int i;
for(i = 0; i < 9; i++)
{
if(clock[i] != 12)
return 0;
}
return 1;
}
queue <CS> q;
//CS tmp;
int BFS()
{
int i, j;
CS f = q.front();
for(i = 1; i <= 9; i++)
{
CS tmp = f;
tmp.n = f.n;
Move(i, tmp.clock);
tmp.n = tmp.n + 1;
tmp.sq[tmp.n - 1] = i;
if(clockok(tmp.clock))
{
q.push(tmp);
return 0; //后面改成用 ans = q.back()即可
//return tmp;
}
else
{
q.push(tmp);
}
}
q.pop();
BFS();
}
int main()
{
fstream in, out;
int i;
CS first, ans;
in.open("clocks.in", ios::in);
out.open("clocks.out", ios::out);
//初始化
for(i = 0; i < 9; i++)
{
in >> first.clock[i];
}
memset(first.sq, 0, sizeof(first.sq));
first.n = 0;
q.push(first);
ans = BFS();
for(i = 0; i < ans.n; i++)
{
out << ans.sq[i] << " ";
}
out << "
";
return 0;
}
①放在USACO上一直通不过 不知道哪里出了问题 输出的n总是等于1 但是BFS递归的次数是对的。在自己的电脑上则是对的
解决：返回局部变量导致的错误 压入queue中再取出则是对的 具体原因还没搞清楚
②遇到新问题 递归溢出了了 递归到时钟旋转5次时会溢出 而有时答案要旋转很多次 如何提高效率？
解决： 这道题用递归大概不可以吧 我写的函数每次递归需要存储过多的变量 在上面程序中递归3000多次就溢出了 后来把递归函数内的各种局部变量都改到外面 改成全局的 不用每次递归创建 但是运行到7000多次也溢出了 对于本题需要4^9 = 363144次递归 远远超出了栈的内存限制 只好用9层循环了
解题关键： 操作的顺序是无关紧要的！！！！ 每种操作不会多于3次 否则就相当于没做了 AC的代码 非常的丑 之后尝试用这个思路对BFS剪枝 但是由于②中的分析原因 剪枝后还是溢出了
学习心得：能用循环的还是用循环吧 循环不好写 或是意义不明的在考虑递归！
//用BFS做不出来 太不爽了 在网上看了别人的思路 每个操作做4次相当于没做 所以只对每个操作做0 - 3次 枚举即可
#include<stdio.h>
int clockadd(int* c)
{
int t = *c;
if(t == 12)
t = 3;
else
t = t + 3;
*c = t;
return 0;
}
int clockok(int * clock)
{
int i;
for(i = 0; i < 9; i++)
{
if(clock[i] != 12)
return 0;
}
return 1;
}
int Move(int m, int *clock)
{
switch(m)
{
case 1:
{
clockadd(&clock[0]); clockadd(&clock[1]); clockadd(&clock[3]); clockadd(&clock[4]);
}
break;
case 2:
{
clockadd(&clock[0]); clockadd(&clock[1]); clockadd(&clock[2]);
}
break;
case 3:
{
clockadd(&clock[1]); clockadd(&clock[2]); clockadd(&clock[4]); clockadd(&clock[5]);
}
break;
case 4:
{
clockadd(&clock[0]); clockadd(&clock[3]); clockadd(&clock[6]);
}
break;
case 5:
{
clockadd(&clock[1]); clockadd(&clock[3]); clockadd(&clock[4]); clockadd(&clock[5]); clockadd(&clock[7]);
}
break;
case 6:
{
clockadd(&clock[2]); clockadd(&clock[5]); clockadd(&clock[8]);
}
break;
case 7:
{
clockadd(&clock[3]); clockadd(&clock[4]); clockadd(&clock[6]); clockadd(&clock[7]);
}
break;
case 8:
{
clockadd(&clock[6]); clockadd(&clock[7]); clockadd(&clock[8]);
}
break;
case 9:
{
clockadd(&clock[4]); clockadd(&clock[5]); clockadd(&clock[7]); clockadd(&clock[8]);
}
break;
default:
break;
}
return 0;
}
int MoveN(int * clock, int * i)
{
int j, k;
for(j = 0; j < 9; j++)
{
for(k = 0; k < i[j]; k++)
{
Move(j+1, clock);
}
}
return 0;
}
int main()
{
FILE *in, *out;
in = fopen("clocks.in", "r");
out = fopen("clocks.out", "w");
int clock[9];
int i[9] = {0}, j, k;
for(j = 0; j < 9; j++)
{
fscanf(in, "%d", &clock[j]);
}
for(i[0] = 0; i[0] < 4; i[0]++)
{
for(i[1] = 0; i[1] < 4; i[1]++)
{
for(i[2] = 0; i[2] < 4; i[2]++)
{
for(i[3] = 0; i[3] < 4; i[3]++)
{
for(i[4] = 0; i[4] < 4; i[4]++)
{
for(i[5] = 0; i[5] < 4; i[5]++)
{
for(i[6] = 0; i[6] < 4; i[6]++)
{
for(i[7] = 0; i[7] < 4; i[7]++)
{
for(i[8] = 0; i[8] < 4; i[8]++)
{
int clockcp[9];
for(j = 0; j < 9; j++)
{
clockcp[j] = clock[j];
}
MoveN(clockcp, i);
if(clockok(clockcp))
{
for(j = 0; j < 9; j++)
{
for(k = 0; k < i[j]; k++)
{
fprintf(out, "%d ", j + 1);
}
}
fseek(out, -1, SEEK_END);
fprintf(out, "
");
return 0;
}
}
}
}
}
}
}
}
}
}
}
又看了下答案的解题思路 有个简便的算法是 先求出单独把每个时钟旋转90度需要对 1 - 9 的操作分别作多少次。 然后，求出输入的矩阵需要分别对 哪些时钟分别旋转几次 把需要的操作步数相加 模4 即可 <---很聪明的方法啊！