首页 » 编程之美 » 正文

[leetcode_36]Valid Sudoku

| 编程之美 | | 暂无评论 | 461 views

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

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 &gt;= 6 &amp;&amp; y &lt; 9)return 5;<br />
        }
        if(x &gt;= 6 &amp;&amp; x &lt; 9) {
            if(y &gt;= 0 &amp;&amp; y &lt; 3)return 6;
            if(y &gt;= 3 &amp;&amp; y &lt; 6)return 7;
            if(y &gt;= 6 &amp;&amp; y &lt; 9)return 8;
        }
    }
    bool GetSetOfPOB(int x,int y){
        set&lt;int&gt;set_tmp;
        set_tmp.clear();
        for(int i = 0;i &lt; 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);<br />
            }
        }
        int region = GetRegionOfBoard(x,y);
        int x_r = (region / 3 + 1)<em>3;
        int y_r = (region % 3 + 1)</em>3;
        for(int i = x_r-3;i &lt; x_r;i++) {
            for(int j = y_r-3;j &lt; 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);<br />
                }
            }
        }
        if(set_tmp.size() == 9)return false;
        set&lt;int&gt;::iterator it;
        for(int i = 1;i &lt;= 9;i++) {
            if(set_tmp.find(i) == set_tmp.end())POB[x][y].set_p.insert(i);
        }
        if(POB[x][y].set_p.size() &lt;= 0)return false;
        return true;
    }
    void Move(int step) {
        if(step &gt;= index) {
            result = true;
            return;
        }
        else {
            if(result == true)return;
            int pi = x[step];
            int pj = y[step];
            set&lt;int&gt;::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 &lt; 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 &lt; 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&lt;vector&lt;char&gt; &gt; &amp;board) {
        for(int i = 0;i &lt; 9;i++) {
            for(int j = 0;j &lt; 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 &lt; 9;i++) {
            for(int j = 0;j &lt; 9;j++) {
                if(POB[i][j].IsExist == false) {
                    if(GetSetOfPOB(i,j) == false)return false;
                }
            }
        }
        index = 0;
        for(int i = 0;i &lt; 9;i++) {
            for(int j = 0;j &lt; 9;j++) {
                if(POB[i][j].IsExist == false) {
                    x[index] = i;
                    y[index++] = j;
                }
            }
        }
        result = false;
        Move(0);
        return result;
    }
};

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

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

<pre><code>}
</code></pre>

<p>};

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

class Solution {
public:
    int bitarray[9];
    int map[9][9];
    bool result;
    int GetRegionOfBoard(int x,int y) {
        if(x&gt;= 0 &amp;&amp; x &lt; 3) {
            if(y &gt;= 0 &amp;&amp; y &lt; 3)return 0;
            if(y &gt;= 3 &amp;&amp; y &lt; 6)return 1;
            if(y &gt;= 6 &amp;&amp; y &lt; 9)return 2;
        }
        if(x &gt;= 3 &amp;&amp; x &lt; 6) {
            if(y &gt;= 0 &amp;&amp; y &lt; 3)return 3;
            if(y &gt;= 3 &amp;&amp; y &lt; 6)return 4;
            if(y &gt;= 6 &amp;&amp; y &lt; 9)return 5;<br />
        }
        if(x &gt;= 6 &amp;&amp; x &lt; 9) {
            if(y &gt;= 0 &amp;&amp; y &lt; 3)return 6;
            if(y &gt;= 3 &amp;&amp; y &lt; 6)return 7;
            if(y &gt;= 6 &amp;&amp; y &lt; 9)return 8;
        }
    }
    bool CheckRows() {
        for(int i = 0;i &lt; 9;i++) {
            int tmp = 0;
            for(int j = 0;j &lt; 9;j++) {
                if(tmp &amp; map[i][j])return false;
                    tmp |= map[i][j];
            }
        }
        return true;
    }
    bool CheckCols() {
        for(int j = 0;j &lt; 9;j++) {
            int tmp = 0;
            for(int i = 0;i &lt; 9;i++) {
                if(tmp &amp; map[i][j])return false;
                    tmp |= map[i][j];
            }
        }
        return true;</p>

<pre><code>}
bool CheckRegion() {
    for(int region = 0;region &amp;lt; 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 &amp;lt; x_r;i++) {
            for(int j = y_r-3;j &amp;lt; y_r;j++) {
                if(tmp &amp;amp; map[i][j])return false;                    
                    tmp = tmp | map[i][j];      
            }
        }
    }
    return true;
}
bool isValidSudoku(vector&amp;lt;vector&amp;lt;char&amp;gt; &amp;gt; &amp;amp;board) {
    for(int i = 0;i &amp;lt; 9;i++) {
        bitarray[i] = (int)pow(2.0,i);
    }
    for(int i = 0;i &amp;lt; 9;i++) {
        for(int j = 0;j &amp;lt; 9;j++) {
            if(board[i][j] == '.') {
                map[i][j] = 0;
            }
            else {
                map[i][j] = bitarray[board[i][j] - '0'-1];
            }
        }
    }
    return CheckRows() &amp;amp;&amp;amp; CheckCols() &amp;amp;&amp;amp; CheckRegion();
}
</code></pre>

<p>};

发表评论