{"id":374,"date":"2018-08-03T18:12:33","date_gmt":"2018-08-03T18:12:33","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=374"},"modified":"2018-08-03T18:19:17","modified_gmt":"2018-08-03T18:19:17","slug":"hdu-6341-%e6%9d%ad%e7%94%b5%e5%a4%9a%e6%a0%a1%e7%ac%ac%e5%9b%9b%e5%9c%ba","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=374","title":{"rendered":"HDU 6341 Problem J. Let Sudoku Rotate \u676d\u7535\u591a\u6821\u7b2c\u56db\u573a"},"content":{"rendered":"

\u9898\u610f<\/h2>\n

\u7ed9\u5b9a16 * 16 \u768416\u8fdb\u5236\u77e9\u9635\uff0c\u6bcf4 * 4\u4e3a\u4e00\u4e2a\u5355\u5143\uff0c\u95ee\u81f3\u5c11\u65cb\u8f6c\u51e0\u4e2a\u5355\u5143\u53ef\u4ee5\u4f7f\u5f97\u6574\u4e2a\u77e9\u9635\u6ee1\u8db3\u6570\u72ec\u7684\u6027\u8d28<\/p>\n

\u9898\u89e3<\/h2>\n

dfs + \u526a\u679d
\n\u7b80\u5355\u7684\u4ee4\u4eba\u53d1\u6307
\n\u6211\u5f53\u521d\u4e3a\u4ec0\u4e48\u6ca1\u53bb\u770b\u8fd9\u9053\u9898<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#include <iostream>\n#include <algorithm>\n#include <cstring>\n#include <vector>\n#include <cmath>\n#include <array>\n\nusing namespace std;\nusing ll = long long;\nconst int maxn = 20;\nint T, ans, tot;\narray<array<char, maxn>, maxn>tmp;\narray<string,maxn>matrix;\narray<int, maxn> vis;\n\nvoid rotate(int x, int y) {\n    for (int i = x; i < x + 4; ++i)\n        for (int j = y; j < y + 4; ++j)\n            tmp[x + j % 4][y + 3 - i % 4] = matrix[i][j];\n\n    for (int i = x; i < x + 4; ++i)\n        for (int j = y; j < y + 4; ++j)\n            matrix[i][j] = tmp[i][j];\n}\n\nbool check(int a, int b) {\n    for (int i = a; i < a + 4; ++i) {\n        tot++;\n        for (int j = 0; j < b + 4; ++j) {\n            if (vis[matrix[i][j]] == tot)\n                return false;\n            vis[matrix[i][j]] = tot;\n        }\n    }\n    for (int i = b; i < b + 4; ++i) {\n        tot++;\n        for (int j = 0; j < a + 4; ++j) {\n            if (vis[matrix[j][i]] == tot)\n                return false;\n            vis[matrix[j][i]] = tot;\n        }\n    }\n    return true;\n}\n\nvoid dfs(int x, int y, int sum) {\n    if (sum >= ans) return;\n    if (x == 4) {\n        ans = min(ans, sum);\n        return;\n    }\n    if (y == 4) {\n        dfs(x + 1, 0, sum);\n        return;\n    }\n    for (int i = 0; i < 4; ++i) {\n        if (check(x * 4, y * 4)) dfs(x, y + 1, sum + i);\n        rotate(x * 4, y * 4);\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    cin >> T;\n    while (T--) {\n        for (int i = 0; i < 16; ++i) {\n            cin >> matrix[i];\n        }\n        for (int i = 0; i < 16; ++i)\n            for (int j = 0; j < 16; ++j)\n                if (isdigit(matrix[i][j])) matrix[i][j] -= '0';\n                else matrix[i][j] -= 'A' - 10;\n        ans = 50;\n        dfs(0, 0, 0);\n        cout << ans << \"\\n\";\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f \u7ed9\u5b9a16 * 16 \u768416\u8fdb\u5236\u77e9\u9635\uff0c\u6bcf4 * 4\u4e3a\u4e00\u4e2a\u5355\u5143\uff0c\u95ee\u81f3\u5c11\u65cb\u8f6c\u51e0\u4e2a\u5355\u5143\u53ef\u4ee5\u4f7f\u5f97\u6574\u4e2a\u77e9\u9635\u6ee1\u8db3\u6570\u72ec\u7684 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,50,51,22],"tags":[],"class_list":["post-374","post","type-post","status-publish","format-standard","hentry","category-c","category-50","category-51","category-22"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-62","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=374"}],"version-history":[{"count":2,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions"}],"predecessor-version":[{"id":378,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions\/378"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}