hdu 1426 Sudoku Killerが泣かせてくれたDFS
4667 ワード
2日間苦しめられた TLE
最初は少しも考えがなかった. おや 失敗を好む ファイト 爆撃機 爆撃爆撃 ゴロゴロと鳴る DFSを壊す に頼る
Sudoku Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1271 Accepted Submission(s): 352
Problem Description
2006年3月10日から11日までの第1回数独世界選手権以来、数独というゲームはますます人々に愛され、重視されている.
2008年北京オリンピックでは、数独を単独種目として試合を行い、優勝者が獲得する可能性のある巨大な賞品--HDUの無料7日間のツアーにlcyの直筆サインとhdu acm teamと記念写真を撮る機会があるという.
だから世界の人々は前に続いて、賞品のために日夜茶飯を訓練した.もちろん初心者linleも含まれていますが、彼は愚かで忍耐力があまりなく、最も基本的な数独問題しかできませんが、賞品をもらいたいと思っています.手伝ってもらえますか.君は答えを彼に伝えればいい,彼にどうすればいいか教えなくてもいい.
数独ゲームのルールは、9 x 9の四角形の中で、数字1-9をスペースに記入し、四角形の各行と各列に1-9という9つの数字を含ませる必要があります.また、スペースに太い線で9つの3 x 3に分割された四角形にも1-9という9つの数字が含まれていることを保証します.例えば、このような問題があるので、よく観察してみてください.この中には行ごとに、列ごとに、3 x 3の格子ごとに1-9という9つの数字が含まれています.
Input
この問題には、各グループの間に空の行で区切られた複数のテストが含まれています.各グループのテストでは、同じ行に隣接する2つの要素が1つのスペースで区切られた9*9のマトリクスが与えられます.このうち1-9はその位置の記入済み数を表し、疑問符(?)は記入する必要がある数を表します.
Output
各テストのセットについて、同じ行に隣接する2つの数を1つのスペースで区切った解を出力します.2組の解の間に空の行が必要です.
各テストデータのセットに対して、解が1つしかないことを保証します.
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output
7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
無数の牛の心血を参考にした
コード:
#include #include int a[10][10]; int flag; int num,cnt; struct haha { int q_x; int q_y; }ques[90];//疑問符の位置を記録するint ok(int x,int y,int n){ int i,j,xx,yy,xxx,yyy; for(i=0;i<9;i+)/縦行のデータが競合しているかどうか if(a[i][x]==n) return 0; for(i=0;i<9;i+)/1行のデータに競合がないか if(a[y][i]==n) return 0; xx = x/3*3; yy = y/3*3; //どの9宮格に属するかを計算します 9つの宮格でデータが衝突しているかどうかを確認します. xxx = xx+3; yyy = yy+3; for(i=yy;i
int i; if(flag) return; if(cnt==num) { flag=1; return ; } for(i=1;i<=9;i++) if(ok(ques[cnt].q_x,ques[cnt].q_y,i)) { a[ques[cnt].q_y][ques[cnt].q_x]=i; dfs(cnt+1); if(flag==1) return; a[ques[cnt].q_y][ques[cnt].q_x]=0; } } int main() { int x,y,i,j,t=0; char ch[2]; while(scanf("%s",&ch)!=EOF) { num=0;cnt=0;flag=0; if(ch[0]!='?') a[0][0]=ch[0]-'0'; else { a[0][0]=0; ques[num].q_y=0;ques[num++].q_x=0; } for(y=0;y<9;y++) { for(x=0;x<9;x++) { if(x==0&&y==0) continue; scanf("%s",&ch); if(ch[0]!='?') a[y][x]=ch[0]-'0'; else { a[y][x]=0; ques[num].q_y=y;ques[num++].q_x=x; } } } dfs(0); if(t++)printf(");//2組の解の間に1行のスペースがあることを明らかにする.つまり、最初の解のセットを印刷するときに空行があってはいけない.その後、印刷するたびに空行を出力しなければならない. for(i=0;i<9;i++) { for(j=0;j<8;j++) { printf("%d ",a[i][j]); } printf("%d",a[i][8]); } // if(t++) printf(""); //ここに置くとフォーマットエラーが発生します.これは最初のテーブルが空の行を印刷した後、印刷が終わるたびに空の行に追随します. } return 0; }
最初の難題 どのようにdfsの中で疑問符の位置を探し当ててまさか一回の検索???答え:主関数の中ですべての疑問符の位置の2番目の難題を記録します 1行に複数の疑問符がある どうやってこの数の全配列を作ってdfsに行かせるの? 疑問符に直接1-9の数字を記入します 3つ目の難題が実行できるかどうかを見てみましょう 正しい答えが一つしかないことをどうやって保証しますか? 自分で誤って問題を理解しました各テストデータに対して1つの解があることを保証します.1つの解を見つけさえすれば、他の解を探す必要はありません.4番目の難題です. 答えはタイムアウト EOFがないとタイムアウトします いくつかの小さい枝切りとテクニックも問題を解決することができます1先に1つの数を入力することを要求するためです 最初は1つの数を入力します 次に、最初の行の数を入力します(最初の行は入力済みのため含まれません). それから2-9行の数を入力してこのように複雑で時間コードの中の方法を浪費するのはとても力があります 先に1つの数を入力して、それからすべて入力した直接continueを遍歴して入力しなくてもいいです いいえタイムアウトします 複数の小さなブロックに分かれているので 複数の9つの宮格に分かれています データを入力するときに配列によって1-9から入力するのに明らかな法則がなければ、x yがどの9つの宮格に位置するかを見つけることができず、0-8から入力すると xx = x/3*3; yy = y/3*3; //この方法でどの9宮格xxx=xx+3に属するかを計算するのは簡単です.yyy=yy+3です. 3千万万2組の解の間に1行のスペースの意味があることを明らかにします4ここの入力は%sを使うのが一番いいです %sがスペースに遭遇したり、車に戻ったりして終了したため、スペースリターン記号は保存されません. %cで あとでgetchar()を追加しなければなりません それでもいいけど複雑 しかもタイムアウトになる タイムアウトになるので簡略化できるところに遭遇したらできるだけ簡略化してみました
最初は少しも考えがなかった. おや 失敗を好む ファイト 爆撃機 爆撃爆撃 ゴロゴロと鳴る DFSを壊す に頼る
Sudoku Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1271 Accepted Submission(s): 352
Problem Description
2006年3月10日から11日までの第1回数独世界選手権以来、数独というゲームはますます人々に愛され、重視されている.
2008年北京オリンピックでは、数独を単独種目として試合を行い、優勝者が獲得する可能性のある巨大な賞品--HDUの無料7日間のツアーにlcyの直筆サインとhdu acm teamと記念写真を撮る機会があるという.
だから世界の人々は前に続いて、賞品のために日夜茶飯を訓練した.もちろん初心者linleも含まれていますが、彼は愚かで忍耐力があまりなく、最も基本的な数独問題しかできませんが、賞品をもらいたいと思っています.手伝ってもらえますか.君は答えを彼に伝えればいい,彼にどうすればいいか教えなくてもいい.
数独ゲームのルールは、9 x 9の四角形の中で、数字1-9をスペースに記入し、四角形の各行と各列に1-9という9つの数字を含ませる必要があります.また、スペースに太い線で9つの3 x 3に分割された四角形にも1-9という9つの数字が含まれていることを保証します.例えば、このような問題があるので、よく観察してみてください.この中には行ごとに、列ごとに、3 x 3の格子ごとに1-9という9つの数字が含まれています.
Input
この問題には、各グループの間に空の行で区切られた複数のテストが含まれています.各グループのテストでは、同じ行に隣接する2つの要素が1つのスペースで区切られた9*9のマトリクスが与えられます.このうち1-9はその位置の記入済み数を表し、疑問符(?)は記入する必要がある数を表します.
Output
各テストのセットについて、同じ行に隣接する2つの数を1つのスペースで区切った解を出力します.2組の解の間に空の行が必要です.
各テストデータのセットに対して、解が1つしかないことを保証します.
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output
7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
無数の牛の心血を参考にした
コード:
#include #include int a[10][10]; int flag; int num,cnt; struct haha { int q_x; int q_y; }ques[90];//疑問符の位置を記録するint ok(int x,int y,int n){ int i,j,xx,yy,xxx,yyy; for(i=0;i<9;i+)/縦行のデータが競合しているかどうか if(a[i][x]==n) return 0; for(i=0;i<9;i+)/1行のデータに競合がないか if(a[y][i]==n) return 0; xx = x/3*3; yy = y/3*3; //どの9宮格に属するかを計算します 9つの宮格でデータが衝突しているかどうかを確認します. xxx = xx+3; yyy = yy+3; for(i=yy;i
int i; if(flag) return; if(cnt==num) { flag=1; return ; } for(i=1;i<=9;i++) if(ok(ques[cnt].q_x,ques[cnt].q_y,i)) { a[ques[cnt].q_y][ques[cnt].q_x]=i; dfs(cnt+1); if(flag==1) return; a[ques[cnt].q_y][ques[cnt].q_x]=0; } } int main() { int x,y,i,j,t=0; char ch[2]; while(scanf("%s",&ch)!=EOF) { num=0;cnt=0;flag=0; if(ch[0]!='?') a[0][0]=ch[0]-'0'; else { a[0][0]=0; ques[num].q_y=0;ques[num++].q_x=0; } for(y=0;y<9;y++) { for(x=0;x<9;x++) { if(x==0&&y==0) continue; scanf("%s",&ch); if(ch[0]!='?') a[y][x]=ch[0]-'0'; else { a[y][x]=0; ques[num].q_y=y;ques[num++].q_x=x; } } } dfs(0); if(t++)printf(");//2組の解の間に1行のスペースがあることを明らかにする.つまり、最初の解のセットを印刷するときに空行があってはいけない.その後、印刷するたびに空行を出力しなければならない. for(i=0;i<9;i++) { for(j=0;j<8;j++) { printf("%d ",a[i][j]); } printf("%d",a[i][8]); } // if(t++) printf(""); //ここに置くとフォーマットエラーが発生します.これは最初のテーブルが空の行を印刷した後、印刷が終わるたびに空の行に追随します. } return 0; }
最初の難題 どのようにdfsの中で疑問符の位置を探し当ててまさか一回の検索???答え:主関数の中ですべての疑問符の位置の2番目の難題を記録します 1行に複数の疑問符がある どうやってこの数の全配列を作ってdfsに行かせるの? 疑問符に直接1-9の数字を記入します 3つ目の難題が実行できるかどうかを見てみましょう 正しい答えが一つしかないことをどうやって保証しますか? 自分で誤って問題を理解しました各テストデータに対して1つの解があることを保証します.1つの解を見つけさえすれば、他の解を探す必要はありません.4番目の難題です. 答えはタイムアウト EOFがないとタイムアウトします いくつかの小さい枝切りとテクニックも問題を解決することができます1先に1つの数を入力することを要求するためです 最初は1つの数を入力します 次に、最初の行の数を入力します(最初の行は入力済みのため含まれません). それから2-9行の数を入力してこのように複雑で時間コードの中の方法を浪費するのはとても力があります 先に1つの数を入力して、それからすべて入力した直接continueを遍歴して入力しなくてもいいです いいえタイムアウトします 複数の小さなブロックに分かれているので 複数の9つの宮格に分かれています データを入力するときに配列によって1-9から入力するのに明らかな法則がなければ、x yがどの9つの宮格に位置するかを見つけることができず、0-8から入力すると xx = x/3*3; yy = y/3*3; //この方法でどの9宮格xxx=xx+3に属するかを計算するのは簡単です.yyy=yy+3です. 3千万万2組の解の間に1行のスペースの意味があることを明らかにします4ここの入力は%sを使うのが一番いいです %sがスペースに遭遇したり、車に戻ったりして終了したため、スペースリターン記号は保存されません. %cで あとでgetchar()を追加しなければなりません それでもいいけど複雑 しかもタイムアウトになる タイムアウトになるので簡略化できるところに遭遇したらできるだけ簡略化してみました