首页 > 代码库 > [USACO 6.4.3]Wisconsin Squares
[USACO 6.4.3]Wisconsin Squares
题解
暴搜即可.
代码
/*TASK:wissquLANG:C++*/#include <cstdio>#include <cstring>using namespace std;char matrix[8][8], path[16][10];bool v[4][4], flag;int ans, num[5] = {3, 3, 3, 4, 3};bool judge(int x0, int y0, int x1, int y1, int k){ for (int i = x0; i <= x1; ++i) for (int j = y0; j <= y1; ++j) if (i >= 0 && i < 4 && j >= 0 && j < 4 && matrix[i][j] == k + ‘A‘) return false; return true;}void dfs(int dep){ if (dep == 16) { if (flag) { for (int i = 0; i < 16; ++i) printf("%s\n", path[i]); flag = false; } ans++; return; } for (int u = 0; u < 5; ++u) if (num[u]) { num[u]--; for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) if (v[i][j] && judge(i-1, j-1, i+1, j+1, u)) { v[i][j] = false; if (flag) { path[dep][0] = u + ‘A‘; path[dep][1] = ‘ ‘; path[dep][2] = i + ‘0‘ + 1; path[dep][3] = ‘ ‘; path[dep][4] = j + ‘0‘ + 1; } char tmp = matrix[i][j]; matrix[i][j] = u + ‘A‘; dfs(dep + 1); matrix[i][j] = tmp; v[i][j] = true; } num[u]++; }}int main(){ freopen("wissqu.in", "r", stdin); freopen("wissqu.out", "w", stdout); for (int i = 0; i < 4; ++i) scanf("%s", matrix[i]); memset(v, true, sizeof(v)); memset(path, 0, sizeof(path)); flag = true; dfs(0); printf("%d\n", ans); return 0;}
[USACO 6.4.3]Wisconsin Squares
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。