課題2
課題2: 幅優先探索で問題を解いてみよう
今回は、ACM ICPC という国際大学対向プログラミングコンテストの2010年国内予選の Problem B: 迷図と命ずを解いてみましょう。
問題の説明は参照先ページを見てもらうのが一番です。 しっかり読んでみましょう。
今回は、この問題を幅優先探索で解いてみましょう。 感じとしては、こんなプログラムを書けば良さそうですよね?
int solve(...) {
enqueue(queue, start);
while(qSize(queue) > 0) {
node_t here = dequeue(queue);
if(北にいける? && 未訪問) {
if(ゴール?) {
return 答え;
}
訪問記録;
enqueue(queue, north);
}
// 南、西、東にも同様
}
// たどり着かなかった場合の処理
}
実装に必要なのは、こんなところでしょう。
- 各方向に進めるかどうか
- queue
- 各地点が訪問済みかどうか、訪問済みの場合、何ステップでたどり着けるか。
といっても、演習時間内ではすぐに解けない人も多いでしょうから、少し下準備しておきます。 以下をダウンロードしてつかってください。
- kadai2.c: 途中まで作成してあるプログラム
- 入力データ: sample.in および B1.in
- 正解データ: sample.ans および B1.ans
- 皆さんのプログラムと正解データの比較は、kadai2.c が勝手にやってくれます。
- ダウンロード手順:
- git を使っている場合は、「ソース管理」の欄を選んで右上の「その他の操作」から「プル」を実行してくれれば、
kadai2
folder が出来上がっているはずです。 - 個別にファイルをダウンロードしたい場合は、こちらからどうぞ。
- git を使っている場合は、「ソース管理」の欄を選んで右上の「その他の操作」から「プル」を実行してくれれば、
プログラムについて簡単な解説をしておきます。
- 基本データ構造
- struct point(point_t): 整数値
x, y
のペア(2次元座標相当) - struct queue(queue_t): Queue データ構造。下記の関数も提供
- int qSize(queue_t * q):
q
のサイズを返す - void enqueue(queue_t * q, ELEM data):
q
にdata
を追加 - ELEM dequeue(queue_t * q):
q
から先頭要素を取り出す
- int qSize(queue_t * q):
- struct point(point_t): 整数値
- 迷図のデータ構造
- 入力データの処理はこちらで準備済み
- 各長方形の領域を、その位置
point_t
であらわし、始点を{0, 0}
, ゴールを{w-1, h-1}
(w: 幅, h: 高さ)とする。 - int canGo(point_t from, point_t direct) を準備
- from: 迷図上の位置
- direct:
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
のいずれかで、進行方向を表す- ちなみに、上記の4方向は
directions
という配列に準備してあります。
- ちなみに、上記の4方向は
- 返り値: from から direct の方向に進めるかどうか。
- main 関数
- 入力データを読み込んで、正しいかチェックする。
- 課題の仕様と違って、入力データを標準入力ではなくファイルから読み込むようになっています。これは、eclipse gdb で操作する際、その方が安定動作したからです。
- int solve(int w, int h)
- 与えられた迷図情報に対して、実際に幅優先で問題を解く部分。
- (
追記
) ゴールに到達できた場合は、最短経路の長さ(経由した四角の数)を返し、到達できない場合は、0
を返してください。 未完成
,皆さんが完成させてください。
main 関数ですが、’‘現状でも、プログラムは動きます。こんな結果がでるはず。
Processing input: kadai2/sample.in
here: (0, 0)
! You failed data No. 0 (result: 0, ans: 4)
here: (0, 0)
here: (0, 0)
! You failed data No. 2 (result: 0, ans: 20)
! I'm sorry you missed 2/3 in kadai2/sample.in!
正解にたどり着いたら、こんな出力になるはず。
Processing input: kadai2/sample
!! Congraturation! You passed all data (3) in sample.in!
Processing input: kadai2/B1
!! Congraturation! You passed all data (90) in B1.in!
ということで、後は、プログラムを頑張って完成させましょう。
各地点が訪問済みかどうか確認するデータ構造つくって、アルゴリズムを完成させることになります
こんな感じの2次元配列を使えばよいでしょう。
使う前に初期化を忘れずに。
課題2の提出物については、後ろをみてください。
データ構造: Queue (待ち行列)
データ構造としては、ある種のリストデータ構造で、 最後から要素を追加して、先頭から要素を取り出す、first in first out (FIFO) 用途です。
enqueue
で要素追加、dequeue
が要素取り出しです。ELEM は、適当な型に #define
でもして使ってください。
typedef struct queue {
int head, tail, size;
ELEM buf[BUFSIZE];
} queue_t;
/****
* queue のサイズを返す
* q: 対象 queue へのポインタ
* 返り値: queue のサイズ
*/
int qSize(queue_t * q);
/****
* queue への要素追加
* q: 対象 queue へのポインタ
* data: 追加をおこなう要素
*/
void enqueue(queue_t * q, ELEM data);
/****
* queue からの要素取り出し
* q: 対象 queue へのポインタ
* 返り値: 取得要素
*/
ELEM dequeue(queue_t * q);
実装は、プログラムの方を見てもらえば良いですが、ring buffer というのを使っています。
構造体を値として扱う
さて、先ほどの queue_t
ですが、
今回は、関数の引数や返り値として、struct point (= point_t)
を使います。
つまり、構造体を「値」として使うことになります。
関数呼び出しのときに、整数値やポインタを使う場合、当然、その値のコピーが渡されるのですが、構造体の場合も、コピーが作成されて引数もしくは返り値として使われます。 まあ、整数値のときと同じだと思ってもらえばOK です。
一方で、Queue の方は、 ポインタ型queue_tp
を用いて管理されています。
当然ですよね?
だって、コピーに要素積めたって、意味ないですから。
「本体」に要素追加するなら、ポインターをつかうしかないってわけです。
/****
* queue への要素追加
* q: 対象 queue へのポインタ
* data: 追加をおこなう要素
*/
void enqueue(queue_t * q, ELEM data) {
assert(q != NULL);
assert(q->size < BUFSIZE);
q->buf[q->tail++]=data;
q->size++;
if(q->tail==BUFSIZE) q->tail = 0;
}
/****
* queue からの要素取り出し
* q: 対象 queue へのポインタ
* 返り値: 取得要素
*/
ELEM dequeue(queue_t * q) {
assert(q != NULL);
assert(q->size > 0);
{
ELEM result = q->buf[q->head++];
q->size--;
if(q->head==BUFSIZE) q->head = 0;
return result;
}
}
課題2の提出物
- 解答プログラム例の公開までに、以下を提出してください。未完全でも必ず全員提出して下さい
- プログラムファイル
- レポート:学番+氏名
- プログラムの解説(半ページ程度)
- コンパイル方及び実行結果(debug 出力が混ざっていても構いません)
- アピールポイントがある人は、その旨解説入れてください。
- 締め切りは
11月6日23:5911月9日12:00
11/7 11/9 に回答例を公開予定です。
自力で解けなかった人は、正解例を参考にレポートを再提出しましょう
- 自分のプログラムはどこで間違っていたか説明すること。
- 正解プログラム例の実行を、デバッガなどでトレースし、正しく動作していることを説明すること。今回の例では、プログラム実行にしたがって、Queue がどのように状態を変化させていったのか、簡単なサンプル(sample の 1つめ 2x3 の盤面のケース)を用いて説明すること。
- 締め切りは
11月13日23:5911月15日23:59
レポートの作成について
課題1で頂いたレポートに対してフィードバックです. 工夫しましょう.