美文网首页
判断数独是否合法

判断数独是否合法

作者: 杰米 | 来源:发表于2016-09-19 00:22 被阅读103次
    请判定一个数独是否有效。
    
    该数独可能只填充了部分数字,其中缺少的数字用 . 表示。
    
     注意事项
    
    一个合法的数独(仅部分填充)并不一定是可解的。我们仅需使填充的空格有效即可。
    
    您在真实的面试中是否遇到过这个题? Yes
    说明
    什么是 数独?
    
    http://sudoku.com.au/TheRules.aspx
    http://baike.baidu.com/subview/961/10842669.htm
    
    
    class Solution {
    public:
        /**
          * @param board: the board
          * @return: wether the Sudoku is valid
          */
        bool isValidSudoku(const vector<vector<char>>& board) {
            for(int i = 0;i < 9;i++) {
                for(int j = 0;j < 9;j++) {
                    int cur = board[i][j];
                    if (cur == '.') {
                        continue;
                    }
                    for(int k=0;k<9;k++) {
                        int temp = board[i][k];
                        if(temp == cur && k != j) {
                            return false;
                        }
                        
                    }
                    for(int k=0;k<9;k++) {
                        int temp = board[k][j];
                        if(temp == cur && k != i) {
                            return false;
                        }
                       
                    }
                    int n = i/3;
                    int m = j/3;
                    for(int p = n * 3;p < n * 3 + 3;p++) {
                        if (p == i ) {
                                continue;
                            }
                        for(int q = m * 3;q < m * 3 + 3;q++) {
                            if ( q == j) {
                                continue;
                            }
                            if(board[p][q] == cur && p != i && q != j) {
                                return false;
                            }
                        }
                    }
                    
                }
            }
            return true;
        }
    };
    

    相关文章

      网友评论

          本文标题:判断数独是否合法

          本文链接:https://www.haomeiwen.com/subject/nrigettx.html