记忆化搜索
#include <iostream> #include <cstring> #include <iomanip> using namespace std; double f[5][5][5][5][5][5][5][5][5]; bool v[5][5][5][5][5][5][5][5][5]; int p[15][5]; double dfs(int p1,int p2,int p3,int p4,int p5, int p6,int p7,int p8,int p9){ if(v[p1][p2][p3][p4][p5][p6][p7][p8][p9]) return f[p1][p2][p3][p4][p5][p6][p7][p8][p9]; v[p1][p2][p3][p4][p5][p6][p7][p8][p9]=1; double t=0.0 ,S=0.0; int b[13]={0,p1,p2,p3,p4,p5,p6,p7,p8,p9,0} ; for(int i=1;i<=9;i++) for(int j=i+1;j<=9;j++){ if(b[i]>0&&b[j]>0&&p[i][b[i]]==p[j][b[j]]){ b[i]--; b[j]--; S++; t+=dfs(b[1],b[2],b[3],b[4],b[5], b[6],b[7],b[8],b[9]); b[i]++,b[j]++; } } if(S>0) f[p1][p2][p3][p4][p5][p6][p7][p8][p9]= t/S; return f[p1][p2][p3][p4][p5][p6][p7][p8][p9]; } int sov(){ memset(v,0,sizeof v); memset(f,0,sizeof f); v[0][0][0][0][0][0][0][0][0]=1; f[0][0][0][0][0][0][0][0][0]=1.0; for(int i=1;i<=9;i++){ string s1,s2,s3,s4; cin>>s1>>s2>>s3>>s4; if(s1=="")return 0; p[i][1]=s1[0]-'0'; p[i][2]=s2[0]-'0'; p[i][3]=s3[0]-'0'; p[i][4]=s4[0]-'0'; } printf("%.6lf\n",dfs(4,4,4,4,4,4,4,4,4)); return 1; } int main(){ while(sov()); }