生活随笔
收集整理的这篇文章主要介绍了
POJ 2286 The Rotation Game IDA*
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
（再一次感谢学长幻灯片）
ID A* 随便自己yy了一下。
额嗯 思路什么的都没有问题 就是改不对。。
无奈地删代码。。。边删边交。 删啊删
哎呦 AC了
。。。
。。。
。。。
找删的那一段 。
oh
原来 d[i]^1!=f 要改成(d[i]^1)!=f 优先级问题 无奈了。。
#include<cstdio>
#include<algorithm>
using namespace std;
char t,a[
25],b[
25],d[]={
0,
2,
4,
7,
3,
1,
6,
5},ch[]={
7,
8,
9,
12,
13,
16,
17,
18};
char R[
8][
7]={{
1,
3,
7,
12,
16,
21,
23},{
23,
21,
16,
12,
7,
3,
1},{
2,
4,
9,
13,
18,
22,
24},{
24,
22,
18,
13,
9,
4,
2},{
11,
10,
9,
8,
7,
6,
5},{
5,
6,
7,
8,
9,
10,
11},{
14,
15,
16,
17,
18,
19,
20},{
20,
19,
18,
17,
16,
15,
14}};
void r(
int x){
int jy=a[R[x][
0]];
for(
char i=
1;i<
7;i++)a[R[x][i-
1]]=a[R[x][i]];a[R[x][
6]]=jy;
}
bool check(){
for(
int i=
1;i<=
7;i++)
if(a[ch[i]]!=a[ch[
0]])
return 0;
return 1;
}
char g(){
char cnt[]={
0,
0,
0};
for(
char i=
0;i<=
7;i++)cnt[a[ch[i]]-
1]++;
return 8-max(cnt[
0],max(cnt[
1],cnt[
2]));
}
bool dfs(
char f,
char x){
if(x>t)
return 0;
for(
char i=
0;i<
8;i++)
if((d[i]^
1)!=f&&g()+x<=t+
1){r(d[i]);b[x]=i+
'A';
if(check()||dfs(d[i],x+
1))
return 1;r(d[i]^
1);}
return 0;
}
int main(){
while(
scanf(
"%d",&a[
1])&&a[
1]){
for(
char i=
2;i<=
24;i++)
scanf(
"%d",&a[i]);
if(check()){
printf(
"No moves needed\n%d\n",a[ch[
0]]);
continue;}
for(t=
1;;t++)
if(dfs(
10,
1))
break;
for(
char i=
1;i<=t;i++)
printf(
"%c",b[i]);
printf(
"\n%d\n",a[ch[
0]]);}
}
#include <cstdio>
using namespace std;
short t,a[
25],b[
25],d[]={
0,
2,
4,
7,
3,
1,
6,
5},ch[]={
7,
8,
9,
12,
13,
16,
17,
18};
short R[
8][
7]={{
1,
3,
7,
12,
16,
21,
23},{
23,
21,
16,
12,
7,
3,
1},{
2,
4,
9,
13,
18,
22,
24},{
24,
22,
18,
13,
9,
4,
2},{
11,
10,
9,
8,
7,
6,
5},{
5,
6,
7,
8,
9,
10,
11},{
14,
15,
16,
17,
18,
19,
20},{
20,
19,
18,
17,
16,
15,
14}};
void r(
int x){
int jy=a[R[x][
0]];
for(
int i=
1;i<
7;i++)a[R[x][i-
1]]=a[R[x][i]];a[R[x][
6]]=jy;}
short max(
short a,
short b,
short c){
int t=a>b?a:b;
return t>c?t:c;}
bool check(){
for(
int i=
1;i<=
7;i++)
if(a[ch[i]]!=a[ch[
0]])
return false;
return true;}
short g(){
int cnt[]={
0,
0,
0};
for(
int i=
0;i<=
7;i++)cnt[a[ch[i]]-
1]++;
return 8-max(cnt[
0],cnt[
1],cnt[
2]);
}
bool dfs(
int f,
int x){
if(x>t)
return false;
for(
int i=
0;i<
8;i++)
if((d[i]^
1)!=f&&g()+x<=t+
1){r(d[i]);b[x]=i+
'A';
if(check()||dfs(d[i],x+
1))
return true;r(d[i]^
1);}
return false;
}
int main(){
while(
scanf(
"%d",&a[
1])&&a[
1]){
for(
int i=
2;i<=
24;i++)
scanf(
"%d",&a[i]);
if(check()){
printf(
"No moves needed\n%d\n",a[ch[
0]]);
continue;}
for(t=
1;;t++)
if(dfs(
10,
1))
break;
for(
int i=
1;i<=t;i++)
printf(
"%c",b[i]);
printf(
"\n%d\n",a[ch[
0]]);}
}
WA 的惨痛教训
最后一次AC 成功把code length刷到第一。
转载于:https://www.cnblogs.com/SiriusRen/p/6532450.html
总结
以上是生活随笔为你收集整理的POJ 2286 The Rotation Game IDA*的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
