{"id":1215,"date":"2024-10-19T09:00:00","date_gmt":"2024-10-19T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1215"},"modified":"2024-09-23T11:46:55","modified_gmt":"2024-09-23T03:46:55","slug":"zerojudge-g596","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-g596\/","title":{"rendered":"ZeroJudge G596: \u52d5\u7dda\u5b89\u6392"},"content":{"rendered":"\n<p>\u4f60\u662f\u4e00\u500b\u904a\u6a02\u5712\u5c55\u5834\u7684\u7ba1\u7406\u54e1\uff0c\u5c55\u5834\u662f\u4e00\u500b\u00a0M\u00d7N\u00a0\u7684\u77e9\u5f62\uff0c\u53ef\u4ee5\u4f7f\u7528\u6728\u6a01\u548c\u7dda\u4f86\u6392\u52d5\u7dda\uff0c\u4f60\u53ef\u4ee5\u6709\u5169\u7a2e\u64cd\u4f5c\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u52a0\u5165\u6728\u6a01 r c 0<br>\u52a0\u4e00\u6728\u6a01\u5728\u00a0(r, c)\uff0c\u4e26\u4e14\u5411\u4ed6\u7684\u4e0a\u4e0b\u5de6\u53f3\u76e1\u91cf\u627e\u96e2\u6700\u8fd1\u7684\u6728\u6a01\u9023\u7dda\uff0c\u984c\u76ee\u4fdd\u8b49\u00a0(r, c)\u00a0\u4e0a\u4e00\u5b9a\u6c92\u6709\u6728\u6a01\uff0c\u82e5\u00a0(r, c)\u00a0\u6709\u7dda\u7d93\u904e\u5247\u5148\u5c07\u90a3\u4e9b\u7dda\u62c6\u6389\u5f8c\u518d\u4f86\u9023\u7dda\u3002<\/li>\n\n\n\n<li>\u79fb\u9664\u6728\u6a01 r c 1<br>(r, c)\u00a0\u62d4\u6728\u6a01\uff0c\u4e26\u628a\u4ed6\u7684\u7dda\u4e5f\u62d4\u6389\uff0c\u4fdd\u8b49\u00a0(r, c)\u00a0\u4e0a\u4e00\u5b9a\u6709\u6728\u6a01\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u7e3d\u5171\u6709\u00a0h\u00a0\u6b21\u64cd\u4f5c\uff0c\u8f38\u51fa\u904e\u7a0b\u4e2d\u6709\u7dda\u548c\u6709\u6728\u6a01\u4f54\u64da\u7a7a\u9593\u7684\u9762\u7a4d\u6700\u5927\u662f\u591a\u5c11\uff0c\u4ee5\u53ca\u00a0h\u00a0\u6b21\u64cd\u4f5c\u5f8c\u6709\u7dda\u548c\u6709\u6728\u6a01\u4f54\u64da\u7a7a\u9593\u7684\u9762\u7a4d\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>\u7bc4\u4f8b\u8f38\u5165<\/th><th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead><tbody><tr><td>\u7b2c\u4e00\u884c\u8f38\u5165\u4e09\u500b\u6b63\u6574\u6578 M\u3001N\u3001H\uff0c\u4ee3\u8868\u5c55\u5834\u7bc4\u570d\u662f M\u00d7N \u4e26\u4e14\u6709 H \u7b46\u64cd\u4f5c\u3002<br>\u63a5\u4e0b\u4f86\u6703\u6709 H \u884c\uff0c\u6bcf\u4e00\u884c\u90fd\u6709\u4e09\u500b\u975e\u8ca0\u6574\u6578 R\u3001C\u3001T\uff0c\u4ee3\u8868\u5728\u4f4d\u7f6e (R, C) \u57f7\u884c\u64cd\u4f5c T\u3002<\/td><td>\u8f38\u51fa\u5169\u500b\u6578\u5b57\u3002<br>\u7b2c\u4e00\u500b\u6578\u5b57\u8868\u793a\uff0c\u64cd\u4f5c\u904e\u7a0b\u4e2d\u6709\u7dda\u548c\u6709\u6728\u6a01\u4f54\u64da\u7a7a\u9593\u7684\u9762\u7a4d\u6700\u5927\u503c\u3002<br>\u7b2c\u4e8c\u500b\u6578\u5b57\u8868\u793a\uff0c\u64cd\u4f5c\u7d50\u675f\u5f8c\u6709\u7dda\u548c\u6709\u6728\u6a01\u4f54\u64da\u7a7a\u9593\u7684\u9762\u7a4d\u3002<\/td><\/tr><tr><td>3 5 6<br>0 0 0<br>0 2 0<br>2 2 0<br>2 0 0<br>2 4 0<br>2 2 1<\/td><td>10<br>6<\/td><\/tr><tr><td>5 5 7<br>2 2 0<br>2 4 0<br>4 4 0<br>4 0 0<br>0 3 0<br>4 3 0<br>4 3 1<\/td><td>12<br>7<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">ZeroJudge G596 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n<p>\u7576\u8981\u63d2\u5165\u6728\u6a01\u6642\u5224\u65b7\u4e0a\u4e0b\u5de6\u53f3\u7684\u6700\u8fd1\u6728\u6a01\uff0c\u4e26\u4e14\u9032\u884c\u727d\u7dda\u3002<\/p>\n\n\n\n<p>\u7576\u8981\u62d4\u9664\u6728\u6a01\u6642\u5224\u65b7\u4e0a\u4e0b\u5de6\u53f3\u7684\u6700\u8fd1\u6728\u6a01\uff0c\u8981\u5224\u65b7\u662f\u5426\u8981\u63a5\u7dda\u6216\u662f\u62d4\u7dda\u3002\u5982\u679c\u540c\u4e00\u500b\u65b9\u5411 (\u7e31\u5411\u6216\u6a6b\u5411) \u6c92\u6709\u5169\u7aef\u90fd\u6709\u6728\u6a01\uff0c\u5c31\u8981\u62d4\u7dda\uff0c\u76f8\u53cd\u7684\u5c31\u8981\u63a5\u7dda\u3002\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u62d4\u548c\u63a5\u6642\u9700\u8981\u5224\u65b7\u76ee\u524d\u5728\u8655\u7406\u7684\u662f\u7e31\u5411\u7684\u7dda\u9084\u662f\u6a6b\u5411\u7684\u7dda\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0d<a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=g596\" target=\"_blank\" rel=\"noreferrer noopener\">ZeroJudge G596: \u52d5\u7dda\u5b89\u6392<\/a><\/h3>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include &lt;iostream&gt;\nusing namespace std;\n\nchar verticalLine(const char ch) {\n    if (ch == &#39;.&#39; || ch == &#39;V&#39;) {\n        return &#39;V&#39;;\n    }\n    return &#39;B&#39;;\n}\n\nchar horizontalLine(const char ch) {\n    if (ch == &#39;.&#39; || ch == &#39;H&#39;) {\n        return &#39;H&#39;;\n    }\n    return &#39;B&#39;;\n}\n\nchar deleteVerticalLine(const char ch) {\n    if (ch == &#39;B&#39;) return &#39;H&#39;;\n    return &#39;.&#39;;\n}\n\nchar deleteHorizontalLine(const char ch) {\n    if (ch == &#39;B&#39;) return &#39;V&#39;;\n    return &#39;.&#39;;\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N, M, H, max = -999, final = 0;\n    cin &gt;&gt; N &gt;&gt; M &gt;&gt; H;\n    char arcade[100][100] = {};\n    for (int i = 0; i&lt;N; i++) {\n        for (int j = 0; j&lt;M; j++) {\n            arcade[i][j] = &#39;.&#39;;\n        }\n    }\n    for (int i = 0; i&lt;H; i++) {\n        int R, C, T;\n        cin &gt;&gt; R &gt;&gt; C &gt;&gt; T;\n        if (T == 0) {\n            arcade[R][C] = &#39;W&#39;;\n            for (int j = R-1; j&gt;=0; j--) {\n                if (arcade[j][C] == &#39;W&#39;) {\n                    for (int k = j+1; k&lt;R; k++) {\n                        arcade[k][C] = verticalLine(arcade[k][C]);\n                    }\n                    break;\n                }\n            }\n            for (int j = R+1; j&lt;N; j++) {\n                if (arcade[j][C] == &#39;W&#39;) {\n                    for (int k = j-1; k&gt;R; k--) {\n                        arcade[k][C] = verticalLine(arcade[k][C]);\n                    }\n                    break;\n                }\n            }\n            for (int j = C-1; j&gt;=0; j--) {\n                if (arcade[R][j] == &#39;W&#39;) {\n                    for (int k = j+1; k&lt;C; k++) {\n                        arcade[R][k] = horizontalLine(arcade[R][k]);\n                    }\n                    break;\n                }\n            }\n            for (int j = C+1; j&lt;M; j++) {\n                if (arcade[R][j] == &#39;W&#39;) {\n                    for (int k = j-1; k&gt;C; k--) {\n                        arcade[R][k] = horizontalLine(arcade[R][k]);\n                    }\n                    break;\n                }\n            }\n        }\n        else {\n            arcade[R][C] = &#39;.&#39;;\n            for (int j = R-1; j&gt;=0; j--) {\n                if (arcade[j][C] == &#39;W&#39;) {\n                    for (int k = j+1; k&lt;R; k++) {\n                        arcade[k][C] = deleteVerticalLine(arcade[k][C]);\n                    }\n                    break;\n                }\n            }\n            for (int j = R+1; j&lt;N; j++) {\n                if (arcade[j][C] == &#39;W&#39;) {\n                    for (int k = j-1; k&gt;R; k--) {\n                        arcade[k][C] = deleteVerticalLine(arcade[k][C]);\n                    }\n                    break;\n                }\n            }\n            for (int j = C-1; j&gt;=0; j--) {\n                if (arcade[R][j] == &#39;W&#39;) {\n                    for (int k = j+1; k&lt;C; k++) {\n                        arcade[R][k] = deleteHorizontalLine(arcade[R][k]);\n                    }\n                    break;\n                }\n            }\n            for (int j = C+1; j&lt;M; j++) {\n                if (arcade[R][j] == &#39;W&#39;) {\n                    for (int k = j-1; k&gt;C; k--) {\n                        arcade[R][k] = deleteHorizontalLine(arcade[R][k]);\n                    }\n                    break;\n                }\n            }\n        }\n        int count = 0;\n        for (int j = 0; j&lt;N; j++) {\n            for (int k = 0; k&lt;M; k++) {\n                if (arcade[j][k] != &#39;.&#39;) count++;\n            }\n        }\n        if (count &gt; max) max = count;\n        if (i == H-1) final = count;\n    }\n    cout &lt;&lt; max &lt;&lt; &quot;\\n&quot; &lt;&lt; final &lt;&lt; &quot;\\n&quot;;\n}\n\n\/\/ZeroJudge G596\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u4f60\u662f\u4e00\u500b\u904a\u6a02\u5712\u5c55\u5834\u7684\u7ba1\u7406\u54e1\uff0c\u5c55\u5834\u662f\u4e00\u500b\u00a0M\u00d7N\u00a0\u7684\u77e9\u5f62\uff0c\u53ef\u4ee5\u4f7f\u7528\u6728\u6a01\u548c\u7dda\u4f86\u6392\u52d5\u7dda\uff0c\u4f60\u53ef\u4ee5\u6709\u5169\u7a2e\u64cd\u4f5c\uff1a \u7e3d\u5171\u6709\u00a0 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[25],"tags":[22,8,11,9],"class_list":["post-1215","post","type-post","status-publish","format-standard","hentry","category-ioi-apcs","tag-22","tag-8","tag-11","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1215","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/comments?post=1215"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1215\/revisions"}],"predecessor-version":[{"id":1217,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1215\/revisions\/1217"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=1215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=1215"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=1215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}