伊莉討論區

標題: 數獨 [打印本頁]

---

作者: andrew33673367    時間: 2014-3-13 12:52 AM     標題: 數獨



輸入的每一組測試資料均為 9 × 9 的矩陣，且全部為 1~9 的數字，每兩組九宮格之間以一空行作為分隔
輸出說明 ：
yes or no
範例輸入 ：
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

1 9 3 2 6 5 4 7 8
7 8 2 3 1 4 9 5 6
4 5 6 9 7 8 1 3 2
2 3 4 8 5 1 6 9 7
9 6 5 4 3 7 2 8 1
8 7 1 6 9 2 3 4 5
3 1 9 5 8 6 7 2 4
5 2 7 1 4 3 8 6 9
6 4 8 7 2 9 5 1 3
範例輸出 ：

no
yes



以下是我的程式碼，怎麼跑都是yes;

1. #include <iostream>
   
2. #include <cmath>
   
3. #include<stdio.h>
   
4. #include<stdlib.h>
   
5. 
   
6. using namespace std;
   
7. int i,j,k,n,c,d;
   
8. int z,x,h;
   
9. void aaa();
   
10. 
    
11. int st[9][9];
    
12. int m[9];
    
13. int main()
    
14. {
    
15.         
    
16.         c=0;
    
17.         for(d=0;d<9;d++){
    
18.                 m[d]=0;
    
19.         }
    
20.         for(z=0;z<9;z++){
    
21.                 for(x=0;x<9;x++){
    
22.                         cin>>st[z][x];
    
23.                 }
    
24.         }
    
25.         aaa();
    
26.         for(h=0;h<9;h++){
    
27.                 if(m[h]>=2){
    
28.                         cout<<"no";
    
29.                         return 0;
    
30.                 }
    
31.         }
    
32.         cout<<"yes";
    
33.         return 0;
    
34. }
    
35. 
    
36. 
    
37. void aaa()
    
38. {
    
39.         for(i=0;i<9;i+=3){
    
40.                 for(j=0;j<9;j+=3){
    
41.                         for(k=i;k<3;k++){
    
42.                                 for(n=j;n<3;n++){
    
43.                                         if(st[0][0]==st[k][n]){
    
44.                                                 m[c]=m[c]+1;
    
45.                                         }
    
46.                                 }
    
47.                         }
    
48.                         c=c+1;
    
49.                 }
    
50.         }
    
51. }

複製代碼

請問是哪裡有問題??

---

作者: 皇臾    時間: 2014-3-13 08:15 AM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: EdisonX    時間: 2014-3-13 12:40 PM

1. **********************************************************************************/
   
2. /*  Problem: a016 "數獨(SUDOKU)"                                                */
   
3. /*  Language: C (844 Bytes)                                                       */
   
4. /*  Result: AC(2ms, 240KB) judge by zeroserver@ZeroJudge                          */
   
5. /*  Author: edisonx at 2011-07-11 16:43:34                                        */
   
6. /**********************************************************************************/
   
7. 
   
8. 
   
9. #include <stdio.h>
   
10. int table[9][9];
    
11. int checkrow_col();
    
12. int check_block();
    
13. int check();
    
14. 
    
15. int main()
    
16. {
    
17.         int i, j;
    
18.         while(scanf("%d", &table[0][0])==1){
    
19.                 for(i=1; i!=9; ++i) scanf("%d", &table[0][i]);
    
20.                 for(i=1; i!=9; ++i)
    
21.                         for(j=0; j!=9; ++j) scanf("%d", &table[i][j]);
    
22.                 puts( (check() ? "yes" : "no"));
    
23.         }
    
24.         return 0;
    
25. }
    
26. 
    
27. int check()
    
28. {
    
29.         if(checkrow_col()) return check_block();
    
30.         return 0;
    
31. }
    
32. 
    
33. int checkrow_col()
    
34. {
    
35.         int i, j, cnt1, cnt2;
    
36.         for(i=0; i!=9; ++i){
    
37.                 for(cnt1=cnt2=j=0; j!=9; ++j)
    
38.                         cnt1+=table[i][j], cnt2+=table[j][i];
    
39.                 if(cnt1!=45 || cnt2!=45) return 0;
    
40.         }
    
41.         return 1;       
    
42. }
    
43. 
    
44. int check_block()
    
45. {
    
46.         int i, j, k, l, cnt;
    
47.         for(i=0; i!=9; i+=3){
    
48.                 for(j=0; j!=9; j+=3){
    
49.                         for(k=cnt=0; k!=3; ++k)
    
50.                                 for(l=0; l!=3; ++l) cnt+=table[i+k][j+l];
    
51.                         if(cnt!=45) return 0;
    
52.                 }
    
53.         }
    
54.         return 1;
    
55. }

複製代碼

---

作者: EdisonX    時間: 2014-3-13 02:15 PM

改了一下，不用偷雞方式，這樣就沒問題了，而且速度更快。

1. /**********************************************************************************/
   
2. /*  Problem: a016 "數獨(SUDOKU)"                                                */
   
3. /*  Language: C (905 Bytes)                                                       */
   
4. /*  Result: AC(0ms, 280KB) judge by this@ZeroJudge                                */
   
5. /*  Author: edisonx at 2014-03-13 14:14:20                                        */
   
6. /**********************************************************************************/
   
7. 
   
8. 
   
9. #include <stdio.h>
   
10. int table[9][9];
    
11. int checkrow_col();
    
12. int check_block();
    
13. int check();
    
14. 
    
15. int main()
    
16. {
    
17.         int i, j;
    
18.         while(scanf("%d", &table[0][0])==1){
    
19.                 for(i=1; i!=9; ++i) scanf("%d", &table[0][i]);
    
20.                 for(i=1; i!=9; ++i)
    
21.                         for(j=0; j!=9; ++j) scanf("%d", &table[i][j]);
    
22.                 puts( (check() ? "yes" : "no"));
    
23.         }
    
24.         return 0;
    
25. }
    
26. 
    
27. int check()
    
28. {
    
29.         if(checkrow_col()) return check_block();
    
30.         return 0;
    
31. }
    
32. 
    
33. int checkrow_col()
    
34. {
    
35.         int i, j;
    
36.         unsigned rst1=0 , rst2=0;
    
37.         for(i=0; i!=9; ++i){
    
38.                 for(rst1=rst2=j=0; j!=9; ++j)
    
39.                         rst1|=(1U<<table[i][j]), rst2|=(1U<<table[j][i]);
    
40.                 if(rst1!=0x3FE || rst2!=0x3FE) return 0;
    
41.         }
    
42.         return 1;        
    
43. }
    
44. 
    
45. int check_block()
    
46. {
    
47.         int i, j, k, l;
    
48.         unsigned rst;
    
49.         for(i=0; i!=9; i+=3){
    
50.                 for(j=0; j!=9; j+=3){
    
51.                         for(k=rst=0; k!=3; ++k)
    
52.                                 for(l=0; l!=3; ++l) rst|=(1U<<table[i+k][j+l]);
    
53.                         if(rst!=0x3FE) return 0;
    
54.                 }
    
55.         }
    
56.         return 1;
    
57. }

複製代碼

---

作者: abz53378    時間: 2014-3-16 02:02 AM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: EdisonX    時間: 2014-3-16 05:41 AM

abz53378 發表於 2014-3-16 02:02 AM
請問一下 1U

這裡要以二進制來看。

(1) 1U << n

左移 n 個 bit，假設 n = 4 的話， 1U<<4 ，二進位得到 1 0000，翻成十進位得到 16

(2) rst | (1U<<n)

將 rst 第 n 個 bit 設成 1。

-----------

所以整體而言，rst | = (1U<<table[ i ][j] ) ;  是在判斷 table[ i ][j] 是不是剛好出現 1~9，如果 table[ i ] 裡的 1~9 都出現過的話， rst 的二進位剛好會是 11 1111 1110，這個值翻成 16 進位就是  0x3FE。用這種方式判別顯得較省力。

---

歡迎光臨 伊莉討論區 (http://www2.eyny.com/)

Powered by Discuz!