「fjWC2015」当小威遇上棋盘
「题目描述」
一个井字形棋盘,上面有24个格子(如下图)。这些格子上面有1,2,3三种数字, 且每种数字有 8 格。一开始,这些格子上的数字是随机分布的。你的任务是移动这些格 子使得中间 8 个格子的数字相同。有 8 种移动方式,分别标记为 A 到 H,可以理解为 拉动 4 条链,如图的变换为“AC”。问至少需要多少次拉动,才能从初始状态到达目标 状态?(保证数据有解)
「输入格式」
从 jing.in 中输入数据
有多组数据。每组数据一行,24 个数字,从上到下从左到右表示棋盘上的数字。以 0 结束数据。
「输出格式」
输出到 jing.out 中 每组数据一行,输出最少移动次数。
「样例输入」
111132323132231222312133 111111112222222233333333 0
「样例输出」
2 4
「样例说明」
第一个数据变换为“AC”。 第二个数据变换为“DDHH”。
「数据规模与约定」
对于 30% 的数据,最大移动次数 ≤ 9,数据组数 ≤ 10。 对于 60% 的数据,最大移动次数 ≤ 12,数据组数 ≤ 20。 对于 100% 的数据,最大移动次数 ≤ 12,数据组数 ≤ 30。
题解
迭代深搜
加上剪枝和估价函数就能过了
对于每个局面计算至少还要多少步能使得中间8个相同
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<map> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,mid; int a[5][8],tmp[5][8],num[5]; int check() { num[1]=num[2]=num[3]=0; num[a[3][4]]++;num[a[4][4]]++; for(int j=3;j<=5;j++) num[a[1][j]]++,num[a[2][j]]++; return max(max(num[1],num[2]),num[3]); } void move(int k,int f) { if(f) { int t=a[k][7];for(int i=7;i>=2;i--)a[k][i]=a[k][i-1]; a[k][1]=t; } else { int t=a[k][1];for(int i=1;i<=6;i++)a[k][i]=a[k][i+1]; a[k][7]=t; } if(k==1)a[3][3]=a[1][3],a[4][3]=a[1][5]; else if(k==2)a[3][5]=a[2][3],a[4][5]=a[2][5]; else if(k==3)a[1][3]=a[3][3],a[2][3]=a[3][5]; else a[1][5]=a[4][3],a[2][5]=a[4][5]; } bool dfs(int deep,int last,int dir) { int t=check(); if(t==8)return 1; if(deep+8-t>mid)return 0; for(int i=1;i<=4;i++) { if(last==i&&(!dir))continue; move(i,1);if(dfs(deep+1,i,1))return 1;move(i,0); } for(int i=1;i<=4;i++) { if(last==i&&dir)continue; move(i,0);if(dfs(deep+1,i,0))return 1;move(i,1); } return 0; } void solve() { int l=0,r=11,ans=-1; while(l<=r) { mid=(l+r)>>1; for(int i=1;i<=4;i++) for(int j=1;j<=7;j++) a[i][j]=tmp[i][j]; if(dfs(0,-1,-1))ans=mid,r=mid-1; else l=mid+1; } if(ans!=-1)printf("%d\n",ans); else puts("10"); } int main() { freopen("jing.in","r",stdin); freopen("jing.out","w",stdout); while(1) { a[1][1]=read();if(!a[1][1])break; a[2][1]=read(); a[1][2]=read();a[2][2]=read(); for(int i=1;i<=7;i++) a[3][i]=read(); a[1][3]=a[3][3];a[2][3]=a[3][5]; a[1][4]=read();a[2][4]=read(); for(int i=1;i<=7;i++) a[4][i]=read(); a[1][5]=a[4][3];a[2][5]=a[4][5]; a[1][6]=read();a[2][6]=read(); a[1][7]=read();a[2][7]=read(); for(int i=1;i<=4;i++) for(int j=1;j<=7;j++) tmp[i][j]=a[i][j]; solve(); } return 0; } |
计数器 9312758
OI 课件=>
OI 课件=>
123不是等价的么，因此对123直接暴力BFS一遍不就好了。。这样状态数不到750000种，并且答案完全可以预处理。。QAQ
小威是您吗QAQ
这我不知道啊有可能
居然没人发现那天的提交记录里就有个小威吗_(:з」∠)_
我看到了TAT
那是我们干的