更好地设计多个函数调用
更好地设计多个函数调用
提问于 2019-10-26 00:49:50
我为一个在线法官网站写了一个数独验证器。https://www.urionlinejudge.com.br/judge/en/problems/view/1383
我的解决方案对于9网格sudoku非常有效，通过使用位集验证每个列行和sudoku 3x3块是否包含1-9的数字，并在数字索引处翻转每一位。
但是，我多次调用ValidateOneBlock()来指定迭代器的范围。
我的直觉告诉我，这种方法可以从根本上更好。如何通过不使用大量调用ValidateOneBlock()的大型if来改进(如果可能)我的代码
#include <iostream>
#include <sstream>
#include <bitset>
namespace Constants
{
constexpr int ROW_COL_SIZE = 9;
const std::string STR_YES = "SIM"; //yes in Portuguese
const std::string STR_NO = "NAO"; //no in Portuguese
}
template<unsigned int N>
class Sudoku
{
private:
int m_matrix[N][N] {{0}};
public:
void ReadRows();
bool IsValid() const;
private:
bool ValidateOneBlock(const int& minRowIndex, const int& maxRowIndex, const int& minColIndex, const int& maxColIndex) const;
};
template<unsigned int N>void Sudoku<N>::ReadRows()
{
for(unsigned int row{0}; row<N; row++)
{
static std::string line;
std::getline(std::cin, line);
std::istringstream issline(line);
int readnum {0};
for(unsigned int i{0}; i<N; i++)
{
issline >> readnum;
m_matrix[row][i] = readnum;
}
}
}
template<unsigned int N>bool Sudoku<N>::IsValid() const
{
//9bit default ctor all zeroes, 000000000
std::bitset<N> bitRow[N];
std::bitset<N> bitCol[N];
for(unsigned int i{0}; i<N; i++)
{
for(unsigned int j{0}; j<N; j++)
{
bitRow[i].flip(m_matrix[i][j]-1); //bitset index is 0 not 1.
bitCol[i].flip(m_matrix[j][i]-1);
}
if(!bitRow[i].all() || !bitCol[i].all()) {
return false;
}
}
/* What ValidateOneBlock() does is verify numbers 1-9 within the Sudoku blocks. These are the indexes
0-0 0-1 0-2 | 0-3 0-4 0-5 | 0-6 0-7 0-8
1-0 1-1 1-2 | 1-3 1-4 1-5 | 1-6 1-7 1-8
2-0 2-1 2-2 | 2-3 2-4 2-5 | 2-6 2-7 2-8
---------------------------------------
3-0 3-1 3-2 | 3-3 3-4 3-5 | 3-6 3-7 3-8
4-0 4-1 4-2 | 4-3 4-4 4-5 | 4-6 4-7 4-8
5-0 5-1 5-2 | 5-3 5-4 5-5 | 5-6 5-7 5-8
---------------------------------------
6-0 6-1 6-2 | 6-3 6-4 6-5 | 6-6 6-7 6-8
7-0 7-1 7-2 | 7-3 7-4 7-5 | 7-6 7-7 7-8
8-0 8-1 8-2 | 8-3 8-4 8-5 | 8-6 8-7 8-8
*/
if(N == Constants::ROW_COL_SIZE)
{
if( ValidateOneBlock(0, 2, 0, 2) &&
ValidateOneBlock(0, 2, 3, 5) &&
ValidateOneBlock(0, 2, 6, 8) &&
ValidateOneBlock(3, 5, 0, 2) &&
ValidateOneBlock(3, 5, 3, 5) &&
ValidateOneBlock(3, 5, 6, 8) &&
ValidateOneBlock(6, 8, 0, 2) &&
ValidateOneBlock(6, 8, 3, 5) &&
ValidateOneBlock(6, 8, 6, 8) )
{
return true;
}
}
return false;
}
template<unsigned int N>
bool Sudoku<N>::ValidateOneBlock(const int& minRowIndex, const int& maxRowIndex,
const int& minColIndex, const int& maxColIndex) const
{
std::bitset<N> bitBlock;
for(int i=minRowIndex; i<=maxRowIndex; i++){
for(int j=minColIndex; j<=maxColIndex; j++){
bitBlock.flip(m_matrix[i][j]-1);
}
}
return bitBlock.all();
}
int main()
{
int instances {0};
std::cin >> instances;
std::cin.clear();
std::cin.ignore();
for(int i{0}; i<instances; i++)
{
std::cout << "Instancia " << i+1 << "\n";
Sudoku<Constants::ROW_COL_SIZE> sudokuInstance;
sudokuInstance.ReadRows();
if(sudokuInstance.IsValid()) {
std::cout << Constants::STR_YES;
} else {
std::cout << Constants::STR_NO;
}
std::cout << "\n\n";
}
return 0;
}回答 2
Stack Overflow用户
发布于 2019-10-26 00:54:49
你实际上有一个3*3的块数组，所以这样的东西应该可以工作：
for ( int row = 0; row < 3; row++ )
{
for ( int column = 0; column < 3; column++ )
{
if (!ValidateOneBlock(row * 3, row * 3 + 2, column * 3, column * 3 + 2))
{
return false;
}
}
}
return true;您可能需要另一个循环来验证这些行：
for ( int i = 0; i < 9; i++ )
{
if (!ValidateOneBlock(i, i, 0, 8))
{
return false;
}
if (!ValidateOneBlock(0, 8, i, i))
{
return false;
}
}Stack Overflow用户
发布于 2019-10-26 01:58:17
我还没有测试过这一点，但对于任何N，假设N是3的倍数，下面的内容应该是有效的。实际上，我认为更好的做法是将Sudoku参数化为两个维度的“块”数量，而不是一个维度上的值数量。这将取消对N的这一特定要求。计算笛卡尔乘积(cellCoordinates)是进一步推广的一个很好的候选方法。
#include <algorithm>
#include <array>
#include <numeric>
...
template<unsigned int N>
bool Sudoku<N>::IsValid() const
{
// 9bit default ctor all zeroes, 000000000
std::bitset<N> bitRow[N];
std::bitset<N> bitCol[N];
for (unsigned int i{0}; i < N; i++)
{
for (unsigned int j{0}; j < N; j++)
{
bitRow[i].flip(m_matrix[i][j] - 1); // bitset index is 0 not 1.
bitCol[i].flip(m_matrix[j][i] - 1);
}
if (!bitRow[i].all() || !bitCol[i].all())
{
return false;
}
}
static_assert(N % 3 == 0, "N should be a multiple of 3");
std::array<int, N / 3> indices;
std::iota(indices.begin(), indices.end(), 0);
std::array<std::pair<int, int>, N> cellCoordinates;
auto curr = cellCoordinates.begin();
for (int i : indices)
for (int j : indices)
*curr++ = std::pair(i, j);
return std::all_of(
cellCoordinates.begin(), cellCoordinates.end(), [this](const auto& c) {
const int rowStart{c.first * 3};
const int rowEnd{rowStart + 2};
const int colStart{c.second * 3};
const int colEnd{colStart + 2};
return ValidateOneBlock(rowStart, rowEnd, colStart, colEnd);
});
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58562654
复制相关文章
相似问题
腾讯云开发者
