\u4e00\u9053\\(IDA*\\)\u7684\u5165\u95e8\u9898\u3002
\n\u9996\u5148\u6211\u4eec\u53d1\u73b0\u79fb\u52a8\u7a7a\u683c\u6bd4\u79fb\u52a8\u9a6c\u66f4\u5bb9\u6613\u3002
\n\u7136\u540e\u8003\u8651\u5982\u4f55\u79fb\u52a8\u3002\u7206\u641c\u9a6c\u7684\u4f4d\u7f6e\u662f\u4e00\u79cd\u6709\u6548\u7684\u505a\u6cd5\u3002
\n\u4f46\u662f\u76f4\u63a5\u7206\u641c\u5f88\u5bb9\u6613\u51fa\u73b0\u4e00\u4e2a\u95ee\u9898\uff1a\u641c\u7d22\u53ef\u80fd\u4f1a\u5728\u4e00\u4e9b\u52a3\u7684\u60c5\u51b5\u4e0b\u641c\u5f88\u4e45\uff0c\u6216\u8005\u641c\u8fdb\u6b7b\u80e1\u540c\u4e0d\u51fa\u6765\u3002
\n\u8fd9\u65f6\u5019\u6211\u4eec\u8bbe\u8ba1\u4e00\u4e2a\u4e1c\u897f\u53eb\u505a\u4f30\u4ef7\u51fd\u6570\\(g_S\\)\uff0c\u5982\u679c\u5f53\u524d\u5c40\u9762\u7684\u82b1\u8d39\\(h_S\\)\u52a0\u4e0a\u4f30\u4ef7\u51fd\u6570\u5927\u4e8e\u82b1\u8d39\u4e0a\u754c\\(f_S\\)\u7684\u8bdd\uff0c\u8fd9\u6761\u9009\u62e9\u652f\u5c31\u662f\u4e0d\u4f18\u7684\u3002
\n\u7136\u540e\u6211\u4eec\u53ef\u4ee5\u679a\u4e3e\u4e0a\u754c\u8fdb\u884c\u641c\u7d22\u3002
\n\u7531\u4e8e\u968f\u7740\u4e0a\u754c\u7684\u589e\u957f\uff0c\u82b1\u8d39\u7684\u589e\u957f\u901f\u5ea6\u6781\u5feb\u2014\u2014\u6bcf\u4e00\u5c42\u7684\u82b1\u8d39\u90fd\u8fdc\u5927\u4e8e\u4e0a\u4e00\u5c42\u7684\u82b1\u8d39\u3002\u6545\u800c\u5c3d\u7ba1\u4e0a\u754c\u5177\u6709\u5355\u8c03\u6027\uff0c\u4f46\u4e8c\u5206\u4e0a\u754c\u5e76\u4e0d\u4f1a\u66f4\u4f18\u3002
\n\uff08\u5176\u5b9e\\(IDA*\\)\u672c\u8d28\u4e0a\u5c31\u662f\u7384\u5b66\u526a\u679d\u5427\u3002\uff09<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n\r\nint nw[6][6];\r\nconst int mp[6][6]={\r\n {0,0,0,0,0,0},\r\n {0,1,1,1,1,1},\r\n {0,0,1,1,1,1},\r\n {0,0,0,-1,1,1},\r\n {0,0,0,0,0,1},\r\n {0,0,0,0,0,0},\r\n};\r\nconst int dx[8]={-2,-2,-1,-1,1,1,2,2};\r\nconst int dy[8]={1,-1,2,-2,2,-2,1,-1};\r\ninline int val(){\r\n int rt=0;\r\n for(int i=1;i<=5;++i){\r\n for(int j=1;j<=5;++j){\r\n if(mp[i][j]!=nw[i][j]){\r\n ++rt;\r\n }\r\n } \r\n }\r\n return rt;\r\n}\r\n\r\ninline int Min(int A,int B){\r\n return A>B?A:B;\r\n}\r\n\r\ninline void Swap(int &X,int &Y){\r\n X^=Y^=X^=Y;\r\n}\r\n\r\ninline bool srch(int dp,int X,int Y,int dm,int lst){\r\n int Nval=val();\r\n if(!Nval){\r\n return 1;\r\n }\r\n if(dp>dm){\r\n return 0;\r\n }\r\n for(int i=0;i<8;++i){\r\n if(i+lst==7){\r\n continue;\r\n }\r\n int NX=X+dx[i],NY=Y+dy[i];\r\n if(NX<1||NY<1||NX>5||NY>5){\r\n continue;\r\n } \r\n Swap(nw[X][Y],nw[NX][NY]);\r\n Nval=val();\r\n if(Nval+dp<=dm+1){\r\n if(srch(dp+1,NX,NY,dm,i)){\r\n return 1;\r\n }\r\n }\r\n Swap(nw[X][Y],nw[NX][NY]);\r\n }\r\n return 0;\r\n}\r\n\r\nvoid init(){\r\n char ch[6];\r\n int SX,SY;\r\n for(int i=1;i<=5;++i){\r\n std::cin>>ch+1;\r\n for(int j=1;j<=5;++j){\r\n nw[i][j]=ch[j]-'0';\r\n if(!isdigit(ch[j])){\r\n nw[i][j]=-1;\r\n SX=i,SY=j;\r\n }\r\n }\r\n }\r\n if(!val()){\r\n puts(\"0\");\r\n return;\r\n }\r\n for(int i=1;i<=15;++i){\r\n if(srch(1,SX,SY,i,-1)){\r\n printf(\"%d\\n\",i);\r\n return;\r\n }\r\n }\r\n puts(\"-1\");\r\n}\r\n\r\nint main(){\r\n int T;\r\n scanf(\"%d\",&T);\r\n while(T--){\r\n init();\r\n }\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\\(IDA*\\)\u7684\u5165\u95e8\u9898\u3002 \u9996\u5148\u6211\u4eec\u53d1\u73b0\u79fb\u52a8\u7a7a\u683c\u6bd4\u79fb\u52a8\u9a6c\u66f4\u5bb9\u6613\u3002 \u7136\u540e\u8003\u8651\u5982\u4f55\u79fb\u52a8\u3002\u7206\u641c\u9a6c\u7684\u4f4d\u7f6e\u662f\u4e00\u79cd\u6709\u6548 … <\/p>\n