首页 > itarticle > 36. valid sudoku

36. valid sudoku

admin 11月 13, 2020 0

题目描述

给一个数独九宫格，判断其是否合法。

题目分析

设置三种标记，行、列、九宫，若在该点，该数没有在行、列、九宫内填过，则将其填入；
否则为非法。

代码

#include <iostream>
#include <vector>
#include <string.h>

const int MAX_SIZE = 10;
class Solution2 {
public:
  bool isValidSudoku(std::vector<std::vector<char> >& board) {
    memset(hang, false, sizeof(hang));
    memset(lie, false, sizeof(lie));
    memset(jiu, false, sizeof(jiu));
    for (unsigned i = 0; i < board.size(); ++i) {
      for (unsigned j = 0; j < board[i].size(); ++j) {
        if (board[i][j] != '.') {
          int c = board[i][j] - '1';
          if (!hang[i][c] && !lie[j][c] && !jiu[i/3*3+j/3][c]) {
            hang[i][c] = true;
            lie[j][c] = true;
            jiu[i/3*3+j/3][c] = true;
          } else {
            std::cout << i << " " << j << std::endl;
            return false;
          }
        }
      }
    }
    return true;
  }
private:
  bool hang[MAX_SIZE][MAX_SIZE];
  bool lie[MAX_SIZE][MAX_SIZE];
  bool jiu[MAX_SIZE][MAX_SIZE];

};

总结

题读错