AcWing 703. 数独检查
原题链接
简单
作者:
王小强
,
2021-02-02 10:50:01
,
所有人可见
,
阅读 357
数学公式计算法
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int t, n;
bool isValidSudoku(vector<vector<int>>& g) {
const int n = g.size();
// check 0: row by row
for (int y = 0; y < n; ++y) {
vector<int> used(n + 1); // used == occupied
for (int x = 0; x < n; ++x) {
int num = g[y][x];
if (used[num]++) return false;
}
}
// check1: column by column
for (int x = 0; x < n; ++x) {
vector<int> used(n + 1);
for (int y = 0; y < n; ++y) {
int num = g[y][x];
if (used[num]++) return false;
}
}
// check2: boxes by boxes
int t = sqrt(n); // 开平方根
for (int boxId = 0; boxId < n; ++boxId) {
vector<int> used(n + 1);
for (int y = boxId / t * t; y < boxId / t * t + t; ++y) {
for (int x = boxId % t * t; x < boxId % t * t + t; ++x) {
int num = g[y][x];
if (used[num]++) return false;
}
}
}
return true;
}
int main() {
cin >> t;
for (int i = 1; i <= t; ++i) {
cin >> n;
vector<vector<int>> g(n * n, vector<int>(n * n));
for (int y = 0; y < n * n; ++y)
for (int x = 0; x < n * n; ++x) cin >> g[y][x];
cout << "Case #" << to_string(i) << ": " << (isValidSudoku(g) ? "Yes" : "No") << endl;
}
return 0;
}
建议加强这道题的测试用例!!!!