(Leetcode que 37)
数独解决器
编写一个程序,通过填充空单元格来解决数独难题。
sudoku解决方案必须满足以下所有规则:
每个数字1-9必须在每一行中准确地出现一次。每个数字1-9必须在每一列中准确地出现一次.每个数字1-9必须在网格的每个93x3子框中精确地出现一次。“.”字符表示空单元格。
制约因素:
board.length == 9
boardi.length == 9
boardi是一个数字或“.”。
保证输入板只有一个解决方案。
class Solution {
public:
bool insertionSafe(vector<vector<char>>& board, int row, int col, int num)
{
for(int k=0;k<9;k++)
{
if(board[row][k] == num)
{
return false;
}
if(board[k][col] == num)
{
return false;
}
int rowFactor = row - (row % 3);
int colFactor = col - (col % 3);
for(int i=rowFactor; i<rowFactor+3; i++)
{
for(int j=colFactor; j<colFactor+3; j++)
{
if(board[i][j] == num)
{
return false;
}
}
}
}
return true;
}
bool solveSudokuHelper(vector<vector<char>>& board, int row, int col)
{
if(row == 9)
{
return true;
}
if(col == 9)
{
return solveSudokuHelper(board, row+1, 0);
}
if(board[row][col] != 0)
{
return solveSudokuHelper(board, row, col+1);
}
for(int k=1; k<=9; k++)
{
if(insertionSafe(board, row, col, k))
{
board[row][col] = k;
if(solveSudokuHelper(board, row, col+1))
{
return true;
}
}
board[row][col] = 0;
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
int row, col;
solveSudokuHelper(board, row, col);
}
};错误消息:==32==ERROR: AddressSanitizer:在pc 0x000000345984 bp 0x7ffc49a143f0 sp 0x7ffc49a143e8上地址0x613000000550上的堆缓冲区-溢出地址为0x6130000550线程T0 #2 0x7faad28ed0b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270000b2)地址0x613000000550是一个野生指针。buggy地址周围的影子字节:0x0c267fff 8050: fa 0x0c267fff 8060: fa 0x0c267fff8070: fa 0x0c267fff8080: fa 0x0c267fff8090: fa =>0x0c267fff80a0: fa fafafa fa 0x0c267fff80b0:fa 0x0c267fff80c0: fa 0x0c267fff80d0: fa 0x0c267fff80e0: fa 0x0c267fff80f0: fa阴影字节图例(一个影子字节代表8个应用程序字节):可寻址: 00部分可寻址: 01 02 03 04 05 06 Heap左侧红区:fa释放的堆区域: fd堆栈左红区: f1堆栈中间红区: f2堆栈右红区: f3堆栈返回后的使用: f5堆栈在作用域后的使用: f8全局红区: f9全局init顺序: f6被用户毒害: f7容器溢出: fc数组cookie: ac帧内对象红区: bb ASan内部: fe左alloca redzone: ca右alloca redzone:cb阴影间隙: cc ==32==ABORTING
发布于 2022-02-26 17:21:52
堆缓冲区溢出和阴影字节被触摸意味着您在程序中的某个地方越界,这会调用未定义的行为。由于这与堆溢出有关,因此您的std::向量可能被错误地访问,很可能是某个地方发生了错误。使用[]访问向量是在绝对确定您处于范围内时使用的,为了进行调试,您可以切换到.at()调用,后者进行边界检查,并在触摸未初始化的内存时抛出。
我看到您有一个从1到9的for循环(i <= 9),这真的是正确的行为吗?因为你的棋盘在任何方向都有9个位置,指数将从0到8。触摸9就会使一切都爆炸。
https://stackoverflow.com/questions/71275249
复制相似问题