Problem J. Let Sudoku Rotate
- Time Limit: 2000/1000 MS (Java/Others)
- Memory Limit: 262144/262144 K (Java/Others)
- Total Submission(s): 530
- Accepted Submission(s): 146
Problem Description
Sudoku is a logic-based, combinatorial number-placement puzzle, which is popular around the world.
In this problem, let us focus on puzzles with 16×16 grids, which consist of 4×4 regions. The objective is to fill the whole grid with hexadecimal digits, i.e. 0123456789ABCDEF, so that each column, each row, and each region contains all hexadecimal digits. The figure below shows a solved sudoku.
Yesterday, Kazari solved a sudoku and left it on the desk. However, Minato played a joke with her - he performed the following operation several times.
* Choose a region and rotate it by 90 degrees counterclockwise.
She burst into tears as soon as she found the sudoku was broken because of rotations.
Could you let her know how many operations her brother performed at least?
Input
The first line of the input contains an integer T (1≤T≤103) denoting the number of test cases.
Each test case consists of exactly 16 lines with 16 characters each, describing a broken sudoku.
Output
For each test case, print a non-negative integer indicating the minimum possible number of operations.
Sample Input
1
681D5A0C9FDBB2F7
0A734B62E167D9E5
5C9B73EF3C208410
F24ED18948A5CA63
39FAED5616400B74
D120C4B7CA3DEF38
7EC829A085BE6D51
B56438F129F79C2A
5C7FBC4E3D08719F
AE8B1673BF42A58D
60D3AF25619C30BE
294190D8EA57264C
C7D1B35606835EAB
AF52A1E019BE4306
8B36DC78D425F7C9
E409492FC7FA18D2 Sample Output
5Hint
The original sudoku is same as the example in the statement.
链接
http://acm.hdu.edu.cn/showproblem.php?pid=6341
题意
有一个由十六进制组成的数独16*16，每一行每一列和每个小区域(4*4)都是由0123456789ABCDEF组成。有一个解好的数独，但是每一次将其中的某个小区域逆时针旋转90度得到了现在的数独（已知），问至少旋转了多少次，也就是将当前数独还原需要顺时针旋转90度多少次。
题解
暴力搜索，每四行组成一行进行dfs，具体见代码。参考了Eliot__的题解。理论时间复杂度$O(4^{16})$实际上由于数独的各种限制条件以及剪枝操作不会超时。
/*
* --------- 0
* | | | | |
* --------- 4
* | | | | |
* --------- 8
* | | | | |
* --------- 12
* | | | | |
* --------- 16
*/
代码
| Status | Accepted |
|---|---|
| Time | 280ms |
| Memory | 1372kB |
| Length | 2443 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[20][20];
char t[5][5];
int vis[20], ans;
void roat(int x, int y) // 旋转操作，(x, y)表示每个小区域的左下角坐标
{
for (int i = 1, a = y; i <= 4; ++i, ++a) // t临时保存旋转后的字符
{
for (int j = 1, b = x; j <= 4; ++j, --b)
t[i][j] = s[b][a];
}
for (int j = 1, a = y; j <= 4; ++j, ++a) // 旋转后的字符传给s
{
for (int i = 4, b = x; i >= 1; --i, --b)
s[b][a] = t[i][j];
}
}
int value(char c) // 获取每个字符的数值
{
if (c >= '0' && c <= '9')
return c - '0';
return c - 'A' + 10;
}
bool check(int x) // 检查x到x-3四行是否合格
{
for (int i = x - 3; i <= x; ++i) // 每行的值为120
{
int sum = 0;
for (int j = 1; j <= 16; ++j)
sum += value(s[i][j]);
if (sum != 120)
return false;
}
for (int i = x - 3; i <= x; ++i) // 每行不能有相同的元素
{
memset(vis, 0, sizeof(vis));
for (int j = 1; j <= 16; ++j) // 一次循环完成
{
if (vis[value(s[i][j])])
return false;
vis[value(s[i][j])] = 1;
}
}
for (int j = 1; j <= 16; ++j) // 每列不能有相同的元素
{
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= x; ++i)
{
if (vis[value(s[i][j])])
return 0;
vis[value(s[i][j])] = 1;
}
}
return true;
}
void dfs(int k, int num) // k表示行数，从4开始（4, 8, 12, 16），num表示旋转次数
{
if (num > ans) // 旋转次数超过最大旋转次数
return ;
if (k == 20) // 到达最后一行
{
ans = min(ans, num);
return ;
}
for (int i = 0; i <= 3; ++i, roat(k, 1)) // 每一行的小区域开始旋转
{
for (int j = 0; j <= 3; ++j, roat(k, 5))
{
for (int p = 0; p <= 3; ++p, roat(k, 9))
{
for (int q = 0; q <= 3; ++q, roat(k, 13))
{
if (!check(k))
continue;
dfs(k + 4, num + i + j + p + q);
}
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
for (int i = 1; i <= 16; ++i) // 输入下标从1开始
scanf("%s", s[i] + 1);
ans = 16 * 4; // 初始化答案
dfs(4, 0);
printf("%d\n", ans);
}
return 0;
}The end.
2018-08-03 星期五