您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C++實(shí)現(xiàn)驗(yàn)證數(shù)獨(dú)的方法”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C++實(shí)現(xiàn)驗(yàn)證數(shù)獨(dú)的方法”吧!
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Example 1:
Input:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: true
Example 2:
Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9and the character '.'.
The given board size is always 9x9.
這道題讓驗(yàn)證一個(gè)方陣是否為數(shù)獨(dú)矩陣,想必?cái)?shù)獨(dú)游戲我們都玩過,就是給一個(gè) 9x9 大小的矩陣,可以分為9個(gè) 3x3 大小的矩陣,要求是每個(gè)小矩陣內(nèi)必須都是1到9的數(shù)字不能有重復(fù),同時(shí)大矩陣的橫縱列也不能有重復(fù)數(shù)字,是一種很經(jīng)典的益智類游戲,經(jīng)常在飛機(jī)上看見有人拿著紙筆在填數(shù),感覺是消磨時(shí)光的利器。這道題給了一個(gè)殘缺的二維數(shù)組,讓我們判斷當(dāng)前的這個(gè)數(shù)獨(dú)數(shù)組是否合法,即要滿足上述的條件。判斷標(biāo)準(zhǔn)是看各行各列是否有重復(fù)數(shù)字,以及每個(gè)小的 3x3 的小方陣?yán)锩媸欠裼兄貜?fù)數(shù)字,如果都無重復(fù),則當(dāng)前矩陣是數(shù)獨(dú)矩陣,但不代表待數(shù)獨(dú)矩陣有解,只是單純的判斷當(dāng)前未填完的矩陣是否是數(shù)獨(dú)矩陣。那么根據(jù)數(shù)獨(dú)矩陣的定義,在遍歷每個(gè)數(shù)字的時(shí)候,就看看包含當(dāng)前位置的行和列以及 3x3 小方陣中是否已經(jīng)出現(xiàn)該數(shù)字,這里需要三個(gè) boolean 型矩陣,大小跟原數(shù)組相同,分別記錄各行,各列,各小方陣是否出現(xiàn)某個(gè)數(shù)字,其中行和列標(biāo)志下標(biāo)很好對(duì)應(yīng),就是小方陣的下標(biāo)需要稍稍轉(zhuǎn)換一下,具體代碼如下:
解法一:
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<vector<bool>> rowFlag(9, vector<bool>(9)); vector<vector<bool>> colFlag(9, vector<bool>(9)); vector<vector<bool>> cellFlag(9, vector<bool>(9)); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') continue; int c = board[i][j] - '1'; if (rowFlag[i][c] || colFlag[c][j] || cellFlag[3 * (i / 3) + j / 3][c]) return false; rowFlag[i][c] = true; colFlag[c][j] = true; cellFlag[3 * (i / 3) + j / 3][c] = true; } } return true; } };
我們也可以對(duì)空間進(jìn)行些優(yōu)化,只使用一個(gè) HashSet 來記錄已經(jīng)存在過的狀態(tài),將每個(gè)狀態(tài)編碼成為一個(gè)字符串,能將如此大量信息的狀態(tài)編碼成一個(gè)單一的字符串還是需要有些技巧的。對(duì)于每個(gè)1到9內(nèi)的數(shù)字來說,其在每行每列和每個(gè)小區(qū)間內(nèi)都是唯一的,將數(shù)字放在一個(gè)括號(hào)中,每行上的數(shù)字就將行號(hào)放在括號(hào)左邊,每列上的數(shù)字就將列數(shù)放在括號(hào)右邊,每個(gè)小區(qū)間內(nèi)的數(shù)字就將在小區(qū)間內(nèi)的行列數(shù)分別放在括號(hào)的左右兩邊,這樣每個(gè)數(shù)字的狀態(tài)都是獨(dú)一無二的存在,就可以在 HashSet 中愉快地查找是否有重復(fù)存在啦,參見代碼如下:
解法二:
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { unordered_set<string> st; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') continue; string t = "(" + to_string(board[i][j]) + ")"; string row = to_string(i) + t, col = t + to_string(j), cell = to_string(i / 3) + t + to_string(j / 3); if (st.count(row) || st.count(col) || st.count(cell)) return false; st.insert(row); st.insert(col); st.insert(cell); } } return true; } };
到此,相信大家對(duì)“C++實(shí)現(xiàn)驗(yàn)證數(shù)獨(dú)的方法”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。