[leetcode_36]Valid Sudoku

这个题，哎哟我只想说我操。
开始题意理解错了，以为是判断某个数独是否有可行解，哎哟我擦，枚举？暴力。
用set集合做了一个各种超时啊：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136


struct PointOfBoard {
    set<int>set_p;
    bool IsExist;
    int val;
    PointOfBoard():IsExist(false),val(-1){set_p.clear();}
};
class Solution {
public:
    PointOfBoard POB[9][9];
    int x[81];
    int y[81];
    int index;
    bool result;
    int GetRegionOfBoard(int x,int y) {
        if(x>= 0 && x < 3) {
            if(y >= 0 && y < 3)return 0;
            if(y >= 3 && y < 6)return 1;
            if(y >= 6 && y < 9)return 2;
        }
        if(x >= 3 && x < 6) {
            if(y >= 0 && y < 3)return 3;
            if(y >= 3 && y < 6)return 4;
            if(y >= 6 && y < 9)return 5;
        }
        if(x >= 6 && x < 9) {
            if(y >= 0 && y < 3)return 6;
            if(y >= 3 && y < 6)return 7;
            if(y >= 6 && y < 9)return 8;
        }
    }
    bool GetSetOfPOB(int x,int y){
        set<int>set_tmp;
        set_tmp.clear();
        for(int i = 0;i < 9;i++) {
            if(POB[x][i].IsExist) {
                int val = POB[x][i].val;
                if(set_tmp.find(val) == set_tmp.end())
                     set_tmp.insert(val);
            }
            if(POB[i][y].IsExist) {
                int val = POB[i][y].val;
                if(set_tmp.find(val) == set_tmp.end())
                    set_tmp.insert(val);
            }
        }
        int region = GetRegionOfBoard(x,y);
        int x_r = (region / 3 + 1)*3;
        int y_r = (region % 3 + 1)*3;
        for(int i = x_r-3;i < x_r;i++) {
            for(int j = y_r-3;j < y_r;j++) {
                if(POB[i][j].IsExist) {
                    int val = POB[i][j].val;
                    if(set_tmp.find(val) != set_tmp.end())
                        set_tmp.insert(val);
                }
            }
        }
        if(set_tmp.size() == 9)return false;
        set<int>::iterator it;
        for(int i = 1;i <= 9;i++) {
            if(set_tmp.find(i) == set_tmp.end())POB[x][y].set_p.insert(i);
        }
        if(POB[x][y].set_p.size() <= 0)return false;
        return true;
    }
    void Move(int step) {
        if(step >= index) {
            result = true;
            return;
        }
        else {
            if(result == true)return;
            int pi = x[step];
            int pj = y[step];
            set<int>::iterator it;
            for(it = POB[pi][pj].set_p.begin();it != POB[pi][pj].set_p.end();it++) {
                if(result == true)return;
                int val = (int)(*it);
                POB[pi][pj].val = val;
                int xtmp[81];
                int ytmp[81];
                int indextmp = 0;
                for(int i = step+1;i < index;i++) {
                    int xi = x[i];
                    int yi = y[i];
                    if(xi == pi || yi == pj || GetRegionOfBoard(xi,yi) == GetRegionOfBoard(pi,pj)) {
                        if(POB[xi][yi].set_p.find(val) != POB[xi][yi].set_p.end()) {
                            xtmp[indextmp] = xi;
                            ytmp[indextmp++] = yi;
                            POB[xi][yi].set_p.erase(val);
                        }
                    }
                }
                Move(step+1);
                for(int i = 0;i < indextmp;i++) {
                    int xi = xtmp[i];
                    int yi = ytmp[i];
                    POB[xi][yi].set_p.insert(val);
                }
                POB[pi][pj].val = -1;
            }
        }
    }
    bool isValidSudoku(vector<vector<char>> &board) {
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(board[i][j] == '.') {
                    POB[i][j].IsExist = false;
                }
                else {
                    POB[i][j].IsExist = true;
                    POB[i][j].val = board[i][j] - '0';
                }
            }
        }
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(POB[i][j].IsExist == false) {
                    if(GetSetOfPOB(i,j) == false)return false;
                }
            }
        }
        index = 0;
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(POB[i][j].IsExist == false) {
                    x[index] = i;
                    y[index++] = j;
                }
            }
        }
        result = false;
        Move(0);
        return result;
    }
};

后来看网上牛人的代码，用int二进制来存，我又写了一版：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150


struct Pointxy {
    int x;
    int y;
    int val;
};
int cmp(Pointxy a,Pointxy b) {
    return a.val < b.val;
}
class Solution {
public:
    int bitarray[9];
    int map[9][9];
    bool result;
    int CountOnes(int v)
    {
        int number = 0;
        while(v)
        {
            v &= (v-1);
            number++;
        }
        return number;
    }
    int GetRegionOfBoard(int x,int y) {
        if(x>= 0 && x < 3) {
            if(y >= 0 && y < 3)return 0;
            if(y >= 3 && y < 6)return 1;
            if(y >= 6 && y < 9)return 2;
        }
        if(x >= 3 && x < 6) {
            if(y >= 0 && y < 3)return 3;
            if(y >= 3 && y < 6)return 4;
            if(y >= 6 && y < 9)return 5;
        }
        if(x >= 6 && x < 9) {
            if(y >= 0 && y < 3)return 6;
            if(y >= 3 && y < 6)return 7;
            if(y >= 6 && y < 9)return 8;
        }
    }
    bool RefeshMap(int x,int y){
        int set_tmp = 0;
        for(int i = 0;i < 9;i++) {
            if(CountOnes(map[x][i]) == 1) {
                set_tmp = set_tmp | map[x][i];
            }
            if(CountOnes(map[i][y]) == 1) {
                set_tmp = set_tmp | map[x][i];
            }
        }
        int region = GetRegionOfBoard(x,y);
        int x_r = (region / 3 + 1)*3;
        int y_r = (region % 3 + 1)*3;
        for(int i = x_r-3;i < x_r;i++) {
            for(int j = y_r-3;j < y_r;j++) {
                if(CountOnes(map[i][j]) == 1) {
                    set_tmp = set_tmp | map[i][j];
                }
            }
        }
        if(set_tmp == 511)return false;
        map[x][y] = 511 - set_tmp;
        return true;
    }
    void Move(Pointxy pxy[81],int index) {
        if(result == true)return;
        if(index <= 0) {
            result = true;
            return;
        }
        else {
            sort(pxy,pxy+index,cmp);
            int pi = pxy[0].x;
            int pj = pxy[0].y;
            for(int ibit = 0;ibit < 9;ibit++) {
                if(result == true)return;
                if(map[pi][pj] & bitarray[ibit]) {
                    map[pi][pj] -= bitarray[ibit];
                    int xtmp[81];
                    int ytmp[81];
                    int indextmp = 0;
                    for(int i = 1;i < index;i++) {
                        int xi = pxy[i].x;
                        int yi = pxy[i].y;
                        if(xi == pi || yi == pj || GetRegionOfBoard(xi,yi) == GetRegionOfBoard(pi,pj)) {
                            if(map[xi][yi] & bitarray[ibit]) {
                                xtmp[indextmp] = xi;
                                ytmp[indextmp++] = yi;
                                map[xi][yi] -= bitarray[ibit];
                            }
                        }
                    }
                    Pointxy pxyt[81];
                    int indext = 0;
                    for(int i = 1;i < index;i++) {
                        pxyt[indext].x = pxy[i].x;
                        pxyt[indext].y = pxy[i].y;
                        pxyt[indext++].val = CountOnes(map[pxyt[indext].x][pxyt[indext].y]);
                    }
                    Move(pxyt,indext);
                    for(int i = 0;i < indextmp;i++) {
                        int xi = xtmp[i];
                        int yi = ytmp[i];
                        map[xi][yi] += bitarray[ibit];
                    }
                    map[pi][pj] += bitarray[ibit];
                }
            }
        }
    }
    bool isValidSudoku(vector<vector<char>> &board) {
        for(int i = 0;i < 9;i++) {
            bitarray[i] = (int)pow(2.0,i);
        }
        int count = 0;
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(board[i][j] == '.') {
                    map[i][j] = 511;
                }
                else {
                    map[i][j] = bitarray[board[i][j] - '0'-1];
                    count++;
                }
            }
        }
        if(count < 17)return false;
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(map[i][j] == 511) {
                    if(RefeshMap(i,j) == false)return false;
                }
            }
        }
        Pointxy pxy[81];
        int index = 0;
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(CountOnes(map[i][j]) != 1) {
                    pxy[index].x = i;
                    pxy[index].y = j;
                    pxy[index].val = CountOnes(map[i][j]);
                }
            }
        }
        result = false;
        Move(pxy,index);
        return result;
}
};

WA???不科学啊？？？
最后WA在一个我一看就无可行解的情况。
实在没办法，查别人的代码。我擦，原来题目要求判断该数独是否是一个当前状态下满足条件的数独，问题简单了好多好多好多啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


class Solution {
public:
    int bitarray[9];
    int map[9][9];
    bool result;
    int GetRegionOfBoard(int x,int y) {
        if(x>= 0 && x < 3) {
            if(y >= 0 && y < 3)return 0;
            if(y >= 3 && y < 6)return 1;
            if(y >= 6 && y < 9)return 2;
        }
        if(x >= 3 && x < 6) {
            if(y >= 0 && y < 3)return 3;
            if(y >= 3 && y < 6)return 4;
            if(y >= 6 && y < 9)return 5;
        }
        if(x >= 6 && x < 9) {
            if(y >= 0 && y < 3)return 6;
            if(y >= 3 && y < 6)return 7;
            if(y >= 6 && y < 9)return 8;
        }
    }
    bool CheckRows() {
        for(int i = 0;i < 9;i++) {
            int tmp = 0;
            for(int j = 0;j < 9;j++) {
                if(tmp & map[i][j])return false;
                    tmp |= map[i][j];
            }
        }
        return true;
    }
    bool CheckCols() {
        for(int j = 0;j < 9;j++) {
            int tmp = 0;
            for(int i = 0;i < 9;i++) {
                if(tmp & map[i][j])return false;
                    tmp |= map[i][j];
            }
        }
        return true;
}
bool CheckRegion() {
    for(int region = 0;region < 9;region++) {
        int x_r = (region / 3 + 1)*3;
        int y_r = (region % 3 + 1)*3;
        int tmp = 0;
        for(int i = x_r-3;i < x_r;i++) {
            for(int j = y_r-3;j < y_r;j++) {
                if(tmp & map[i][j])return false;                    
                    tmp = tmp | map[i][j];      
            }
        }
    }
    return true;
}
bool isValidSudoku(vector<vector<char>> &board) {
    for(int i = 0;i < 9;i++) {
        bitarray[i] = (int)pow(2.0,i);
    }
    for(int i = 0;i < 9;i++) {
        for(int j = 0;j < 9;j++) {
            if(board[i][j] == '.') {
                map[i][j] = 0;
            }
            else {
                map[i][j] = bitarray[board[i][j] - '0'-1];
            }
        }
    }
    return CheckRows() && CheckCols() && CheckRegion();
}
};