leetCode 36. Valid Sudoku(數獨) 哈希

36. Valid Sudoku(合法數獨)

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

關于數獨的簡介：

There are just 3 rules to Sudoku.

1.Each row must have the numbers 1-9 occuring just once.

2.Each column must have the numbers 1-9 occuring just once.

3.And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

題目大意：

判斷一個給定的二維數組是否是一個合法的數獨矩陣。

思路:

采用set這一容器，來進行去重。

1.判斷每一行是否合法。

2.判斷每一列是否合法。

3.判斷每一個九宮格是否合法。

代碼如下：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) 
    {
    	set<char> mySet;
    	//1.判斷每一行是否合法
    	for (int row = 0; row < 9; row++)
    	{
    	    //cout<<"檢測行:"<<row<<endl;
    		for (int column = 0; column < 9; column++)
    		{
    			if (board[row][column] == '.')
    			{
    				continue;
    			}
    			if (mySet.find(board[row][column]) == mySet.end())
    			{
    				mySet.insert(board[row][column]);
    			}
    			else
    			{
    				return false;
    			}
    		}
    		mySet.clear();
    	}
    	
    	//2.判斷每一列是否合法
    	for (int row = 0; row < 9; row++)
    	{
    	    //cout<<"檢測列:"<<row<<endl;
    		for (int column = 0; column < 9; column++)
    		{
    			if (board[column][row] == '.')
    			{
    				continue;
    			}
    			if (mySet.find(board[column][row]) == mySet.end())
    			{
    				mySet.insert(board[column][row]);
    			}
    			else
    			{
    				return false;
    			}
    		}
    		mySet.clear();
    	}
    
    	//3.判斷每一個九宮格是否合法
    	for (int row = 0; row < 9; row += 3)
    	{
    		for (int column = 0; column < 9; column += 3)
    		{
    			for (int i = row; i < row + 3; i++)
    			{
    				for (int j = column; j < column + 3; j++)
    				{
    					if (board[i][j] == '.')
    					{
    						continue;
    					}
    					if (mySet.find(board[i][j]) == mySet.end())
    					{
    						mySet.insert(board[i][j]);
    					}
    					else
    					{
    						return false;
    					}
    				}
    			}
    			mySet.clear();
    		}
    	}
    	return true;
    }
};

2016-08-13 12:21:54