{"id":403,"date":"2022-10-06T20:45:52","date_gmt":"2022-10-06T12:45:52","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=403"},"modified":"2024-09-12T09:32:20","modified_gmt":"2024-09-12T01:32:20","slug":"%e9%a2%98%e8%a7%a3-p1162-%e3%80%90%e5%a1%ab%e6%b6%82%e9%a2%9c%e8%89%b2%e3%80%91","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=403","title":{"rendered":"\u9898\u89e3 P1162 \u3010\u586b\u6d82\u989c\u8272\u3011"},"content":{"rendered":"<p>ps\uff1a\u672c\u9898\u9898\u89e3\u5df2\u7ecf70\u591a\u7bc7\u4e86&#8230;\u4f46\u662f\u7ffb\u4e86\u7ffb\u7adf\u7136\u6ca1\u6709\u968f\u673a\u5316\u7684\u5199\u6cd5\uff0c\u4e8e\u662f\u6597\u80c6\u63d0\u4ea4\u4e00\u7bc7hhh<\/p>\n<p>\u91cd\u8981\uff1a<em>\u8fd9\u4e2a\u5199\u6cd5\u6709\u5c0f\u6982\u7387\u4f1a\u9519\uff0c\u4f46\u662f\u80dc\u5728\u53c8\u5feb\u53c8\u7b80\u5355\uff0c\u6ca1\u6709\u601d\u7ef4\u96be\u5ea6\uff0c\u800c\u4e14\u5f88\u6709\u610f\u601dXD\uff0c\u5982\u679c\u662f\u8003\u573a\u4e0a\u8fd8\u53ef\u4ee5\u7528\u6765\u9a97\u5206<\/em><\/p>\n<p>\u57fa\u672c\u601d\u8def\u5982\u4e0b:<\/p>\n<ul>\n<li>\n<p>\u968f\u673a\u751f\u6210\u4e00\u4e2a\u70b9\uff0c\u5224\u65ad\u8fd9\u4e2a\u70b9\u662f\u5426\u5728\u73af\u5185\uff0c\u5982\u679c\u5728\uff0c\u5c31\u4ece\u8fd9\u4e2a\u70b9\u5f00\u59cbfloodfill\uff08\u65e0\u8111\u6cfc\u6c34\u586b\u5145\uff09\uff0c\u5982\u679c\u4e0d\u5728\uff0c\u5c31\u91cd\u627e\u4e00\u4e2a\u70b9<\/p>\n<p>\u90a3\u4e48\u5982\u4f55\u5224\u65ad\u4e00\u4e2a\u70b9\u5728\u73af\u5185\u5462\uff1f\u8fd9\u91cc\u7684\u601d\u8def\u5f88\u7b80\u5355:<\/p>\n<\/li>\n<li>\n<p>\u5982\u679c\u5411\u56db\u4e2a\u65b9\u5411\u8d70\u90fd\u80fd\u78b0\u52301,\u5c31\u5728\u73af\u5185\uff0c\u53cd\u4e4b\u4e0d\u5728<\/p>\n<p>\u8fd9\u4e2a\u505a\u6cd5\u5f53\u7136\u4e0d\u662f\u4fdd\u8bc1\u6b63\u786e\u7684\u505a\u6cd5\uff0c\u800c\u4e14\u6709\u53ef\u80fd\u88ab\u5361\uff08\u6bd4\u5982\u8bf4\u6709\u4e2a\u53ea\u6709\u4e00\u4e2a\u5c0f\u53e3\u7684\u5047\u73af\uff09\u4f46\u662f\u770b\u4e0b\u6570\u636e\u8303\u56f4\uff0c<code>n \\leq30<\/code>\uff0c\u4e5f\u5c31\u662f\u8bf4\u5982\u679c\u4e0d\u662f\u5f88\u523b\u610f\u7684\u5361\uff0c\u6211\u4eec\u4ecd\u53ef\u4ee5\u671f\u671b\u968f\u673a\u70b9\u751f\u6210\u5728\u73af\u5185\uff0c\u6b63\u786e\u7387\u5e94\u8be5\u4e0d\u9519\uff0c\u4e8b\u5b9e\u8bc1\u660e\uff0c\u76f4\u63a5A\u4e86&#8230;<\/p>\n<p><a href=\"https:\/\/www.luogu.org\/record\/24090249\">\u8bb0\u5f55<\/a><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"language-cpp\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nconst int MAXN=1000;\nconst int dx[]={0,0,-1,0,1},\n          dy[]={0,1,0,-1,0};\n\/\/\u65b9\u5411\u6570\u7ec4\uff0c\u4e0d\u5199\u5927\u5c0f\u4ee3\u8868\u89c6\u521d\u59cb\u503c\u60c5\u51b5\u800c\u5b9a\nint a[MAXN][MAXN];\nint n;\n\nbool chk(int x,int y){\n    if(a[x][y]==1)return false;\n    \/\/\u8fd9\u91cc\u8981\u6ce8\u610f\uff0c\u5982\u679c\u672c\u6765\u5c31\u662f1\u5c31\u522b\u627e\u4e86\uff0c\u76f4\u63a5\u8fd4\u56de\n    bool v1=false,v2=false,v3=false,v4=false;\n    for(int i=1;i&lt;=n &amp;&amp; x+i&lt;=n;i++)\n        if(a[x+i][y]==1 )\n            v1=true;\n    for(int i=1;i&lt;=n &amp;&amp; y+i&lt;=n;i++)\n        if(a[x][y+i]==1 )\n            v2=true;\n    for(int i=1;i&lt;=n &amp;&amp; x-i&gt;=0;i++)\n        if(a[x-i][y]==1 )\n            v3=true;\n    for(int i=1;i&lt;=n &amp;&amp; y-i&gt;=0;i++)\n        if(a[x][y-i]==1 )\n            v4=true;\n    return v1 &amp;&amp; v2 &amp;&amp; v3 &amp;&amp; v4;\n}\n\nbool vis[MAXN][MAXN]={0};\nvoid fld_fill(int x,int y){\n    if(a[x][y]==1 || vis[x][y])return ;\n    \/\/\u5982\u679c\u78b0\u5230\u8fb9\u754c\u6216\u8005\u6cfc\u8fc7\u7684\u70b9\u5c31\u8fd4\u56de\n    vis[x][y]=true;\n    a[x][y]=2;\n    for(int i=1;i&lt;=4;++i)\n        fld_fill(x+dx[i],y+dy[i]);\n}\n\nint main(){\n    srand(rand());\/\/\u968f\u673a\u79cd\u5b50\n    scanf(&quot;%d&quot;,&amp;n);\n    for(int i=1;i&lt;=n;++i)\n        for(int j=1;j&lt;=n;++j)\n            scanf(&quot;%d&quot;,&amp;a[i][j]);\n\n    while(true){\n        int x=rand()%n+1,y=rand()%n+1;\n        \/\/\u6211\u4eec\u7684\u70b9\u7684\u5750\u6807\u5e94\u8be5\u662f1-n\u4e4b\u95f4\u7684\n        bool flag=chk(x,y);\n        if(flag){\/\/\u5982\u679c\u5728\u73af\u5185\u5c31\u6cfc\u6c34\uff0c\u5426\u5219\u518d\u627e\u4e00\u4e2a\u70b9\n            fld_fill(x,y);\n            for(int i=1;i&lt;=n;++i){\n                for(int j=1;j&lt;=n;++j)\n                    printf(&quot;%d &quot;,a[i][j]);\n                printf(&quot;\\n&quot;);\n            }\n            return 0;\n        }\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>ps\uff1a\u672c\u9898\u9898\u89e3\u5df2\u7ecf70\u591a\u7bc7\u4e86&#8230;\u4f46\u662f\u7ffb\u4e86\u7ffb\u7adf\u7136\u6ca1\u6709\u968f\u673a\u5316\u7684\u5199\u6cd5\uff0c\u4e8e\u662f\u6597 [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-403","post","type-post","status-publish","format-standard","hentry","category-2"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=403"}],"version-history":[{"count":2,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/403\/revisions"}],"predecessor-version":[{"id":742,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/403\/revisions\/742"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}