Valid Sudoku 判断数独是否可解

时间:2021-01-13 02:38:30

题目:

点击打开链接

解答:

只需要判断现在已有的元素是否有冲突,不需要判断是否可解。

分别遍历行 列 和9宫格 用map判断是否存在重复元素。


代码:

 class Solution {
 public:
	 bool isValidSudoku(vector<vector<char> > &board) {
		 int n = 9;
		 map<char, bool> have;
		 for (int i = 0; i < n; i++)
		 {
			 have.clear();
			 for (int j = 0; j < n; j++)
			 {
				 if (board[i][j] != '.')
				 {
					 if (have.find(board[i][j]) == have.end())
						 have[board[i][j]] = true;
					 else
						 return false;
				 }
			 }
		 }
		 for (int i = 0; i < n; i++)
		 {
			 have.clear();
			 for (int j = 0; j < n; j++)
			 {
				 if (board[j][i] != '.')
				 {
					 if (have.find(board[j][i]) == have.end())
						 have[board[j][i]] = true;
					 else
						 return false;
				 }
			 }
		 }
		 for (int i = 0; i < 3; i++)
		 {
			 for (int j = 0; j < 3; j++)
			 {
				 have.clear();
				 for (int k = 3 * i; k < 3 * i + 3; k++)
				 {
					 for (int m = 3 * j; m < 3 * j + 3; m++)
					 {
						 if (board[k][m] != '.')
						 {
							 if (have.find(board[k][m]) == have.end())
								 have[board[k][m]] = true;
							 else
								 return false;
						 }
					 }
				 }
			 }
		 }
		 return true;
	 }
 };