{"id":190,"date":"2011-08-23T12:34:50","date_gmt":"2011-08-23T04:34:50","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=190"},"modified":"2020-06-04T12:35:24","modified_gmt":"2020-06-04T04:35:24","slug":"%e7%99%be%e7%bb%83-2754-%e5%85%ab%e7%9a%87%e5%90%8e","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=190","title":{"rendered":"\u767e\u7ec3 2754 \u516b\u7687\u540e"},"content":{"rendered":"\n
\/*\n\u8457\u540d\u7684\u516b\u7687\u540e\u95ee\u9898\nDFS+\u56de\u6eaf\n\u7531\u4e8e\u6bcf\u4e00\u884c\u6709\u4e14\u53ea\u6709\u4e00\u4e2a\u7687\u540e\n\u6240\u4ee5\u9012\u5f52\u5bf9\u6bcf\u4e00\u884c\u8fdb\u884c\u904d\u5386\u5373\u53ef\n\u5f88\u591a\u5730\u65b9\u90fd\u4e0d\u5b8c\u5584\n\u7a0d\u540e\u8d34\u51fa\u6539\u8fdb\u7248\u4ee3\u7801\n*\/\n#define LOCAL\n#include<iostream>\n#include<cstring>\n#include<string>\nusing namespace std;\nint map[10][10],queen[100],nqueen=0;\nbool legal(int x,int y)\/\/\u5224\u65ad\u5f53\u524d\u4f4d\u7f6e\u662f\u5426\u53ef\u653e\n{\n\tint i,j;\n\tfor(i=1;i<=8;i++)\n\t{\n\t\tif(i!=x&&map[i][y]==1)\n\t\t\treturn false;\n\t}\n\tfor(i=x,j=y;i>=1&&j>=1;i--,j--)\n\t{\n\t\tif(i!=x&&map[i][j]==1)\n\t\t\treturn false;\n\t}\n\tfor(i=x,j=y;i>=1&&j<=8;i--,j++)\n\t{\n\t\tif(i!=x&&map[i][j]==1)\n\t\t\treturn false;\n\t}\n\tfor(i=x,j=y;i<=8&&j>=1;i++,j--)\n\t{\n\t\tif(i!=x&&map[i][j]==1)\n\t\t\treturn false;\n\t}\n\tfor(i=x,j=y;i<=8&&j<=8;i++,j++)\n\t{\n\t\tif(i!=x&&map[i][j]==1)\n\t\t\treturn false;\n\t}\n\treturn true;\n}\nvoid getqueen()\/\/\u5b58\u50a8\u5f97\u5230\u7684\u516b\u7687\u540e\u5e8f\u5217\n{\n\tint sum=0,i,j,t=1;\n\tfor(i=8;i>=1;i--)\n\t{\n\t\tj=1;\n\t\twhile(map[i][j]!=1)\n\t\t\tj++;\n\t\tsum+=j*t;\n\t\tt*=10;\n\t}\n\tqueen[nqueen++]=sum;\n}\nvoid DFS(int m)\/\/\u6df1\u641c\u904d\u5386m\u4ee3\u8868\u641c\u7d22\u6df1\u5ea6\u4e5f\u4ee3\u8868\u68cb\u76d8\u884c\u6570\n{\n\tif(m>8) return;\/\/\u653e\u7f6e\u5b8c\u6bd5\u8fd4\u56de\n\tint i;\n\tfor(i=1;i<=8;i++)\/\/\u5bf9\u7b2cm\u884c\u7684\u5404\u4e2a\u683c\u5b50\u8fdb\u884c\u904d\u5386\n\t{\n\t\tif(!map[m][i]&&legal(m,i))\/\/\u5982\u679c\u5f53\u524d\u4f4d\u7f6e\u53ef\u653e\u7f6e\u4e00\u4e2a\u7687\u540e\n\t\t{\n\t\t\t\tmap[m][i]=1;\/\/\u6807\u8bb0\u4e3a\u5df2\u653e\u7f6e\n\t\t\t\tDFS(m+1);\/\/\u641c\u7d22\u4e0b\u4e00\u884c\n\t\t\t\tif(m==8)\/\/\u5982\u679c\u516b\u4e2a\u7687\u540e\u90fd\u5df2\u7ecf\u653e\u7f6e\u5b8c\u6bd5\n\t\t\t\t\tgetqueen();\/\/\u4fdd\u5b58\u7687\u540e\u5e8f\u5217\n\t\t\t\tmap[m][i]=0;\/\/\u53cd\u6807\u8bb0\u5f53\u524d\u4f4d\u7f6e\n\t\t}\n\t}\n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\t\tint ncase,n;\n\t\tmemset(map,0,sizeof(map));\n\t\tDFS(1);\/\/\u4ece\u7b2c\u4e00\u884c\u5f00\u59cb\u653e\u7f6e\n\t\tcin>>ncase;\n\t\twhile(ncase--)\n\t\t{\n\t\t\tcin>>n;\n\t\t\tcout<<queen[n-1]<<endl;\n\t\t}\n\t\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-190","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/190","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=190"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/190\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=190"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=190"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=190"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}