sc10note/honsensample_single.c解説
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
since1995
開始行:
[[sc10note]]
*使い方 [#g522f649]
コンパイル (sc10.hが必要)
gcc honsensample_single.c -o honsensample_single
実行
./honsensample_single prob00.in
実行のところで「prob00.in」の箇所は問題ファイルの名前を書...
*ファイルの中身 [#m3bc1c5e]
-9行目:「MAXSIZE」はsc10.hで定義されています.
-16行目:「sc10_init("teamname");」の「teamname...
-29行目:「compute」を「compute2」に変更しても,結果は変...
**compute2の中身 [#f60595a9]
compute2は「探索木による列挙」の簡単な場合を実装していま...
70 //答えを計算する:goto有り版(goto無し版と計算内容...
71 int compute2(int m, int n, int k, char table[MAXSI...
引数は問題文中のm,n,kと広場を表すtableです.広場の左上隅...
72 int i,j,tmpresult;
73 int blank_x=-1, blank_y = -1;
74 tmpresult = 0;
75 for(i=0; i<m; i++) {
76 for(j=0; j<n; j++) {
77 if(table[i][j] == '.') {
78 blank_x = i;
79 blank_y = j;
80 goto loop_break;
81 }
82 }
83 }
84 loop_break:
85
左上隅から右に向かって順に見ていき,障害物のない場所 (空...
CENTER:&ref(compute1.png);
それが見つかったら,goto文により,84行目に飛び,次の処理...
86 if(blank_x == -1){
87 return 1;
88 }
89
blank_xが-1のとき,すなわち,広場がレンガで埋め尽くされて...
90 tmpresult = 0;
出力となるtmpresultを0に初期化します.
91 if(blank_y+1 < n && table[blank_x][blank_y+1] ==...
92 table[blank_x][blank_y] = table[blank_x][blank...
93 tmpresult = compute2(m, n, k, table);
94 table[blank_x][blank_y+1] = '.';
95 }
blank_xとblank_yの決め方から,見つかった空白の上と左は必...
CENTER:&ref(compute2.png);
93行目では更新されたtableに対してcompute2を再帰呼び出しす...
96 if(blank_x+1 < m && table[blank_x+1][blank_y] ==...
97 table[blank_x][blank_y] = table[blank_x+1][bla...
98 tmpresult = (tmpresult + compute2(m, n, k, tab...
99 table[blank_x+1][blank_y] = '.';
100 }
101 table[blank_x][blank_y] = '.';
96行目から101行目までは,見つけた空白から下のはみ出るよう...
CENTER:&ref(compute3.png);
98行目では,更新されたtableに対してcompute2を再帰呼び出し...
102 return tmpresult;
計算結果であるtmpresultを返します.
103 }
これで,正しく計算ができました.
*computeの中身 [#mc622343]
compute2とほとんど変わりません.goto文を使う代わりに,bla...
終了行:
[[sc10note]]
*使い方 [#g522f649]
コンパイル (sc10.hが必要)
gcc honsensample_single.c -o honsensample_single
実行
./honsensample_single prob00.in
実行のところで「prob00.in」の箇所は問題ファイルの名前を書...
*ファイルの中身 [#m3bc1c5e]
-9行目:「MAXSIZE」はsc10.hで定義されています.
-16行目:「sc10_init("teamname");」の「teamname...
-29行目:「compute」を「compute2」に変更しても,結果は変...
**compute2の中身 [#f60595a9]
compute2は「探索木による列挙」の簡単な場合を実装していま...
70 //答えを計算する:goto有り版(goto無し版と計算内容...
71 int compute2(int m, int n, int k, char table[MAXSI...
引数は問題文中のm,n,kと広場を表すtableです.広場の左上隅...
72 int i,j,tmpresult;
73 int blank_x=-1, blank_y = -1;
74 tmpresult = 0;
75 for(i=0; i<m; i++) {
76 for(j=0; j<n; j++) {
77 if(table[i][j] == '.') {
78 blank_x = i;
79 blank_y = j;
80 goto loop_break;
81 }
82 }
83 }
84 loop_break:
85
左上隅から右に向かって順に見ていき,障害物のない場所 (空...
CENTER:&ref(compute1.png);
それが見つかったら,goto文により,84行目に飛び,次の処理...
86 if(blank_x == -1){
87 return 1;
88 }
89
blank_xが-1のとき,すなわち,広場がレンガで埋め尽くされて...
90 tmpresult = 0;
出力となるtmpresultを0に初期化します.
91 if(blank_y+1 < n && table[blank_x][blank_y+1] ==...
92 table[blank_x][blank_y] = table[blank_x][blank...
93 tmpresult = compute2(m, n, k, table);
94 table[blank_x][blank_y+1] = '.';
95 }
blank_xとblank_yの決め方から,見つかった空白の上と左は必...
CENTER:&ref(compute2.png);
93行目では更新されたtableに対してcompute2を再帰呼び出しす...
96 if(blank_x+1 < m && table[blank_x+1][blank_y] ==...
97 table[blank_x][blank_y] = table[blank_x+1][bla...
98 tmpresult = (tmpresult + compute2(m, n, k, tab...
99 table[blank_x+1][blank_y] = '.';
100 }
101 table[blank_x][blank_y] = '.';
96行目から101行目までは,見つけた空白から下のはみ出るよう...
CENTER:&ref(compute3.png);
98行目では,更新されたtableに対してcompute2を再帰呼び出し...
102 return tmpresult;
計算結果であるtmpresultを返します.
103 }
これで,正しく計算ができました.
*computeの中身 [#mc622343]
compute2とほとんど変わりません.goto文を使う代わりに,bla...
ページ名: