\u4e4b\u524d\u7684\u89e3\u6cd5\u662f\u51e0\u5e74\u524d\u7684\uff0c\u52c9\u52c9\u5f3a\u5f3a\u80fd\u505a\u51fa\u6765\uff0c\u7edd\u5bf9\u7b97\u4e0d\u4e0a\u4f18\u96c5\uff0c\u5982\u4eca\u91cd\u505a\u4e86\uff0c\u8fd9\u662f\u7b2c\u4e8c\u7248<\/p>\n
<\/p>\n
#include <iostream>\r\n#include <vector>\r\n\r\nclass Solution {\r\npublic:\r\n std::vector<std::vector<int>> getResult() {\r\n std::vector<std::vector<int>> result;\r\n\r\n std::vector<int> cur;\r\n dfs(result, 8, cur);\r\n return result;\r\n }\r\n\r\nprivate:\r\n bool can_place(int target, const std::vector<int>& cur, int col) {\r\n std::vector<std::vector<bool>> matrix;\r\n for (int i = 0; i < target; i++) {\r\n matrix.push_back(std::vector<bool>(target, false));\r\n }\r\n\r\n for (int row = 0; row < cur.size(); row++) {\r\n int col = cur[row];\r\n for (int i = 0; i < target; i++) {\r\n matrix[row][i] = true;\r\n matrix[i][col] = true;\r\n int new_val = row + col - i;\r\n if (new_val >= 0 && new_val < target)\r\n matrix[i][new_val] = true;\r\n new_val = i - row + col;\r\n if (new_val >= 0 && new_val < target)\r\n matrix[i][new_val] = true;\r\n }\r\n }\r\n\r\n return !matrix[cur.size()][col];\r\n }\r\n\r\n void dfs(std::vector<std::vector<int>>& result, int target, const std::vector<int>& cur) {\r\n if (cur.size() == target) {\r\n result.push_back(cur);\r\n return;\r\n }\r\n\r\n for (int col = 0; col < target; col++) {\r\n auto new_cur = cur;\r\n if (!can_place(target, cur, col))\r\n continue;\r\n\r\n new_cur.push_back(col);\r\n dfs(result, target, new_cur);\r\n }\r\n }\r\n};\r\n\r\nint main() {\r\n auto result = Solution().getResult();\r\n for (int i = 0; i < result.size(); i++) {\r\n std::cout << std::endl;\r\n for (int j = 0; j < result[i].size(); j++) {\r\n std::cout << result[i][j] << \" \";\r\n }\r\n }\r\n return 0;\r\n}\r\n<\/pre>\n <\/p>\n
<\/p>\n
\u7b2c\u4e09\u7248\u51fa\u6765\u4e86<\/p>\n
\u7b2c\u4e09\u7248\u7528\u4e86\u4e2a\u7f13\u5b58matrix\uff0c\u901f\u5ea6\u4f1a\u6bd4\u7b2c\u4e8c\u79cd\u5feb<\/p>\n
#include <iostream>\r\n#include <vector>\r\n\r\nclass Solution {\r\npublic:\r\n std::vector<std::vector<int>> get_result() {\r\n std::vector<std::vector<int>> result;\r\n\r\n std::vector<int> cur;\r\n dfs(result, 8, cur);\r\n return result;\r\n }\r\n\r\nprivate:\r\n std::vector<std::vector<bool>> create_matrix(int target, const std::vector<int>& cur) {\r\n auto tmp_row = std::vector<bool>(target, false);\r\n std::vector<std::vector<bool>> matrix(target, tmp_row);\r\n for (int row = 0; row < cur.size(); row++) {\r\n const int col = cur[row];\r\n for (int i = 0; i < target; i++) {\r\n matrix[i][col] = true;\r\n matrix[row][i] = true;\r\n\r\n if (col + row - i >= 0 && col + row - i < target)\r\n matrix[i][col + row - i] = true;\r\n if (col - row + i >= 0 && col - row + i < target)\r\n matrix[i][col - row + i] = true;\r\n }\r\n }\r\n return matrix;\r\n }\r\n\r\n void dfs(std::vector<std::vector<int>>& result, int target, const std::vector<int>& cur) {\r\n if (cur.size() == target) {\r\n result.push_back(cur);\r\n return;\r\n }\r\n\r\n auto matrix = create_matrix(target, cur);\r\n for (int col = 0; col < target; col++) {\r\n if (matrix[cur.size()][col])\r\n continue;\r\n auto new_cur = cur;\r\n new_cur.push_back(col);\r\n dfs(result, target, new_cur);\r\n }\r\n }\r\n};\r\n\r\nint main() {\r\n auto result = Solution().get_result();\r\n std::cout << \"result count: \" << result.size() << std::endl;\r\n for (int i = 0; i < result.size(); i++) {\r\n std::cout << std::endl;\r\n for (int j = 0; j < result[i].size(); j++) {\r\n std::cout << result[i][j] << \" \";\r\n }\r\n }\r\n return 0;\r\n}\r\n<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e4b\u524d\u7684\u89e3\u6cd5\u662f\u51e0\u5e74\u524d\u7684\uff0c\u52c9\u52c9\u5f3a\u5f3a\u80fd\u505a\u51fa\u6765\uff0c<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[120],"class_list":["post-3882","post","type-post","status-publish","format-standard","hentry","tag-04-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/3882","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=3882"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/3882\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=3882"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=3882"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=3882"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}