![\"QQ\u56fe\u724720210128112830.png\"](\"https:\/\/cdn.acwing.com\/media\/article\/image\/2021\/01\/28\/46888_e80f009261-QQ\u56fe\u724720210128112830.png\")
<\/p>\n\n\n\n\u591c\u7a7a\u6df1\u5904\uff0c\u95ea\u4eae\u7684\u661f\u661f\u4ee5\u661f\u7fa4\u7684\u5f62\u5f0f\u51fa\u73b0\u5728\u4eba\u4eec\u773c\u4e2d\uff0c\u5f62\u6001\u4e07\u5343\u3002<\/p>\n\n\n\n
\u4e00\u4e2a\u661f\u7fa4\u662f\u6307\u4e00\u7ec4\u975e\u7a7a\u7684\u5728\u6c34\u5e73\uff0c\u5782\u76f4\u6216\u5bf9\u89d2\u7ebf\u65b9\u5411\u76f8\u90bb\u7684\u661f\u661f\u7684\u96c6\u5408\u3002<\/p>\n\n\n\n
\u4e00\u4e2a\u661f\u7fa4\u4e0d\u80fd\u662f\u4e00\u4e2a\u66f4\u5927\u661f\u7fa4\u7684\u4e00\u90e8\u5206\u3002<\/p>\n\n\n\n
\u661f\u7fa4\u53ef\u80fd\u662f\u76f8\u4f3c\u7684\u3002<\/p>\n\n\n\n
\u5982\u679c\u4e24\u4e2a\u661f\u7fa4\u7684\u5f62\u72b6\u3001\u5305\u542b\u661f\u661f\u7684\u6570\u76ee\u76f8\u540c\uff0c\u90a3\u4e48\u65e0\u8bba\u5b83\u4eec\u7684\u671d\u5411\u5982\u4f55\uff0c\u90fd\u8ba4\u4e3a\u5b83\u4eec\u662f\u76f8\u4f3c\u7684\u3002<\/p>\n\n\n\n
\u901a\u5e38\u661f\u7fa4\u53ef\u80fd\u6709 8 \u79cd\u671d\u5411\uff0c\u5982\u4e0b\u56fe\u6240\u793a\uff1a<\/p>\n\n\n\n
\u73b0\u5728\uff0c\u6211\u4eec\u7528\u4e00\u4e2a\u4e8c\u7ef4 01 \u77e9\u9635\u6765\u8868\u793a\u591c\u7a7a\uff0c\u5982\u679c\u4e00\u4e2a\u4f4d\u7f6e\u4e0a\u7684\u6570\u5b57\u662f 1\uff0c\u90a3\u4e48\u8bf4\u660e\u8fd9\u4e2a\u4f4d\u7f6e\u4e0a\u6709\u4e00\u4e2a\u661f\u661f\uff0c\u5426\u5219\u8fd9\u4e2a\u4f4d\u7f6e\u4e0a\u7684\u6570\u5b57\u5e94\u8be5\u662f 0\u3002<\/p>\n\n\n\n
\u7ed9\u5b9a\u4e00\u4e2a\u591c\u7a7a\u4e8c\u7ef4\u77e9\u9635\uff0c\u8bf7\u4f60\u5c06\u5176\u4e2d\u7684\u6240\u6709\u661f\u7fa4\u7528\u5c0f\u5199\u5b57\u6bcd\u8fdb\u884c\u6807\u8bb0\uff0c\u6807\u8bb0\u65f6\u76f8\u4f3c\u661f\u7fa4\u7528\u540c\u4e00\u5b57\u6bcd\uff0c\u4e0d\u76f8\u4f3c\u661f\u7fa4\u7528\u4e0d\u540c\u5b57\u6bcd\u3002<\/p>\n\n\n\n
\u6807\u6ce8\u661f\u7fa4\u5c31\u662f\u6307\u5c06\u661f\u7fa4\u4e2d\u6240\u6709\u7684 1 \u66ff\u6362\u4e3a\u5c0f\u5199\u5b57\u6bcd\u3002<\/p>\n\n\n\n
\u8f93\u5165\u683c\u5f0f<\/strong> \u7b2c\u4e8c\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 $H$\uff0c\u8868\u793a\u77e9\u9635\u9ad8\u5ea6\u3002<\/p>\n\n\n\n \u63a5\u4e0b\u6765 $H$ \u884c\uff0c\u6bcf\u884c\u5305\u542b\u4e00\u4e2a\u957f\u5ea6\u4e3a $W$ \u7684 01 \u5e8f\u5217\uff0c\u7528\u6765\u63cf\u8ff0\u6574\u4e2a\u591c\u7a7a\u77e9\u9635\u3002<\/p>\n\n\n\n \u8f93\u51fa\u683c\u5f0f<\/strong> \u7528\u5c0f\u5199\u5b57\u6bcd\u6807\u8bb0\u661f\u7fa4\u7684\u65b9\u6cd5\u5f88\u591a\uff0c\u6211\u4eec\u5c06\u6574\u4e2a\u8f93\u51fa\u8bfb\u53d6\u4e3a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u80fd\u591f\u4f7f\u5f97\u8fd9\u4e2a\u5b57\u7b26\u4e32\u5b57\u5178\u5e8f\u6700\u5c0f\u7684\u6807\u8bb0\u65b9\u5f0f\uff0c\u5c31\u662f\u6211\u4eec\u60f3\u8981\u7684\u6807\u8bb0\u65b9\u5f0f\u3002<\/p>\n\n\n\n \u8f93\u51fa\u8fd9\u4e2a\u6807\u8bb0\u65b9\u5f0f\u6807\u51fa\u7684\u6700\u7ec8\u4e8c\u7ef4\u77e9\u9635\u3002<\/p>\n\n\n\n \u6570\u636e\u8303\u56f4<\/strong> \u8f93\u5165\u6837\u4f8b<\/strong><\/p>\n\n\n\n \u8f93\u51fa\u6837\u4f8b<\/strong><\/p>\n\n\n\n \u8fd9\u9053\u9898\u5173\u952e\u5728\u4e8e\u5224\u65ad\u662f\u5426\u6709\u76f8\u540c\u7684\u5f62\u72b6\uff0c\u800c\u5f62\u72b6\u8fd9\u4e2a\u7279\u5f81\u53ef\u4ee5\u4ece \u9898\u76ee\u63cf\u8ff0 \u591c\u7a7a\u6df1\u5904\uff0c\u95ea\u4eae\u7684\u661f\u661f\u4ee5\u661f\u7fa4\u7684\u5f62\u5f0f\u51fa\u73b0\u5728\u4eba\u4eec\u773c\u4e2d\uff0c\u5f62\u6001\u4e07\u5343\u3002 \u4e00\u4e2a\u661f\u7fa4\u662f\u6307\u4e00\u7ec4\u975e\u7a7a\u7684\u5728\u6c34\u5e73\uff0c\u5782\u76f4\u6216\u5bf9\u89d2 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[30,61,60],"class_list":["post-86","post","type-post","status-publish","format-standard","hentry","category-mess","tag-dfs","tag-usaco-training-5-1","tag-60"],"_links":{"self":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/86","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/comments?post=86"}],"version-history":[{"count":2,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/86\/revisions"}],"predecessor-version":[{"id":101,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/86\/revisions\/101"}],"wp:attachment":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media?parent=86"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/categories?post=86"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/tags?post=86"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 $W$\uff0c\u8868\u793a\u77e9\u9635\u5bbd\u5ea6\u3002<\/p>\n\n\n\n
\u8f93\u51fa\u6807\u8bb0\u5b8c\u6240\u6709\u661f\u7fa4\u540e\u7684\u4e8c\u7ef4\u77e9\u9635\u3002<\/p>\n\n\n\n
$0\u2264W,H\u2264100$,
$0\u2264 \u661f\u7fa4\u6570\u91cf \u2264500$,
$0\u2264 \u4e0d\u76f8\u4f3c\u661f\u7fa4\u6570\u91cf \u226426$,
$1\u2264 \u661f\u7fa4\u4e2d\u661f\u661f\u7684\u6570\u91cf \u2264160$<\/p>\n\n\n\n\u6837\u4f8b<\/h4>\n\n\n\n
23\n15\n10001000000000010000000\n01111100011111000101101\n01000000010001000111111\n00000000010101000101111\n00000111010001000000000\n00001001011111000000000\n10000001000000000000000\n00101000000111110010000\n00001000000100010011111\n00000001110101010100010\n00000100110100010000000\n00010001110111110000000\n00100001110000000100000\n00001000100001000100101\n00000001110001000111000<\/code><\/pre>\n\n\n\na000a0000000000b0000000\n0aaaaa000ccccc000d0dd0d\n0a0000000c000c000dddddd\n000000000c0b0c000d0dddd\n00000eee0c000c000000000\n0000e00e0ccccc000000000\nb000000e000000000000000\n00b0f000000ccccc00a0000\n0000f000000c000c00aaaaa\n0000000ddd0c0b0c0a000a0\n00000b00dd0c000c0000000\n000g000ddd0ccccc0000000\n00g0000ddd0000000e00000\n0000b000d0000f000e00e0b\n0000000ddd000f000eee000<\/code><\/pre>\n\n\n\n
\n\n\n\n\u6837\u4f8b\u89e3\u91ca\u8fd9\u91cc\u5c31\u4e0d\u753b\u4e86\uff0c\u8be6\u60c5\u53c2\u8003\u9898\u76ee<\/strong><\/h3>\n\n\n\n
\u9898\u76ee\u5206\u6790\uff1a<\/h3>\n\n\n\n
\u6bcf\u4e00\u4e2a\u661f\u661f\u4e0e\u5176\u4ed6\u661f\u661f\u7684\u8ddd\u79bb\u4e4b\u548c<\/code>\u6765\u552f\u4e00\u8868\u793aps\uff1a<\/code>\uff08\u8fd9\u4e5f\u662f\u521a\u5b66\u5230\u7684\uff09<\/p>\n\n\n\n\u7b97\u6cd5\u6b65\u9aa4\uff1a<\/h4>\n\n\n\n
\n
1<\/code>\u5173\u952e\u5b57\uff0c\u5b58\u5165\u5750\u6807\u6570\u7ec4v<\/code>\u5e76dfs<\/code>\u9012\u5f52\u641c\u7d22\u9644\u8fd1\u7684\u661f\u661f<\/li>\n\n\n\ndouble<\/code>\u578b\u6570\u7ec4\u6765\u5224\u65ad<\/li>\n\n\n\nc<\/code><\/li>\n\n\n\nps\uff1a<\/code>\u4ee3\u7801\u4e2d\u6709\u8f83\u8be6\u7ec6\u7684\u6ce8\u91ca<\/li>\n<\/ul>\n\n\n\nC++\u4ee3\u7801<\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <cmath>\n\nusing namespace std;\n#define ff first \/\/\u8fd9\u91ccff ss\u66ff\u4ee3pair\u4e2d\u7684first\uff0csecond\n#define ss second\ntypedef long long LL;\ntypedef pair<int,int> PII;\nint w,h;\nchar g[110][110];\/\/\u56fe\nint run[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};\/\/\u65b9\u5411\u6570\u7ec4\nvector<double>ma;\/\/\u4fdd\u5b58\u6bcf\u4e00\u4e2a\u65b9\u5757\u503c\u5bf9\u5e94\u7684\u5b57\u7b26\nvector<PII>v;\/\/\u7528\u6765\u8bb0\u5f55\u4e00\u6b21\u641c\u7d22\u4e2d\u7684\u5750\u6807\n\n\nvoid dfs(int x,int y)\n{\n g[x][y]='0';\n v.push_back({x,y});\/\/\u5750\u6807\u63a8\u5165\n for(int i=0;i<8;i++)\n {\n int tx=x+run[i][0];\n int ty=y+run[i][1];\n if(g[tx][ty]=='0'||tx>=h||ty>=w||tx<0||ty<0) continue;\n dfs(tx,ty);\n }\n}\n\ndouble get_dis()\/\/\u8ba1\u7b97\u8be5\u661f\u7fa4\u6bcf\u4e00\u4e2a\u661f\u661f\u5230\u5176\u4ed6\u661f\u661f\u7684\u8ddd\u79bb\n{\n double sum=0;\n for(int i=0;i<v.size();i++)\n for(int j=i+1;j<v.size();j++)\n sum+=sqrt((v[i].ff-v[j].ff)*(v[i].ff-v[j].ff)+(v[i].ss-v[j].ss)*(v[i].ss-v[j].ss));\n return sum;\n}\n\nvoid fill(char c)\/\/\u628a\u56fe\u586b\u4e0a\u76f8\u5e94\u7684\u5b57\u6bcdc\n{\n for(int i=0;i<v.size();i++)\n g[v[i].first][v[i].second]=c;\n}\n\nchar get_check(double x)\/\/\u5224\u65ad\u8be5\u7279\u5f81\u8ddd\u79bb\u662f\u5426\u5b58\u5728\u8fc7\n{\n for(int i=0;i<ma.size();i++)\n {\n if(fabs(ma[i]-x)<1e-6) return (char)('a'+i);\/\/\u5b58\u5728\u76f4\u63a5\u8fd4\u56de\u8fd9\u4e2a\u5b57\u6bcd\n }\n char newc='a'+ma.size();\/\/ma\u4e2d\u4e0d\u5b58\u5728\u8fd9\u4e2a\u8ddd\u79bb\uff08\u5f62\u72b6\uff09\n ma.push_back(x);\n return newc;\/\/\u8fd4\u56de\u65b0\u5b57\u6bcd\n}\n\nint main()\n{\n cin>>w>>h;\n for(int i=0;i<h;i++)\/\/\u8bfb\u5165\u56fe\n for(int j=0;j<w;j++)\n cin>>g[i][j];\n\n for(int i=0;i<h;i++)\n {\n for(int j=0;j<w;j++)\n {\n if(g[i][j]=='1')\n {\n dfs(i,j);\n double sum=get_dis();\/\/\u5f97\u5230\u5f53\u524d\u8fd9\u4e2a\u661f\u7fa4\u7684\u8ddd\u79bb\n char c=get_check(sum);\/\/\u5f97\u5230\u8fd9\u4e2a\u8ddd\u79bb\u4e0b\u7684\u5b57\u6bcdc\n fill(c);\/\/\u8fd9\u4e2a\u661f\u7fa4\u5168\u90e8\u586b\u4e0a\u8fd9\u4e2a\u5b57\u7b26\n v.clear();\/\/\u6e05\u7a7a\u8fd9\u4e2a\u5750\u6807\u6570\u7ec4\n }\n }\n }\n for(int i=0;i<h;i++)\/\/\u8f93\u51fa\u56fe\n {\n for(int j=0;j<w;j++)\n printf(\"%c\",g[i][j]);\n printf(\"\\n\");\n }\n\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"