課題２

課題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 が出来上がっているはずです。
  • 個別にファイルをダウンロードしたい場合は、こちらからどうぞ。

プログラムについて簡単な解説をしておきます。

• 基本データ構造

  • struct point(point_t): 整数値 x, y のペア（2次元座標相当）
  • struct queue(queue_t): Queue データ構造。下記の関数も提供
    • int qSize(queue_tp q): q のサイズを返す
    • void enqueue(queue_tp q, ELEM data): q に data を追加
    • ELEM dequeue(queue_tp q): q から先頭要素を取り出す

• 迷図のデータ構造

  • 入力データの処理はこちらで準備済み
  • 各長方形の領域を、その位置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} のいずれかで、進行方向を表す
      • ちなみに、上記の４方向は directions という配列に準備してあります。
    • 返り値： 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!

ということで、後は、プログラムを頑張って完成させましょう。 各地点が訪問済みかどうか確認するデータ構造つくって、アルゴリズムを完成させることになります こんな感じの２次元配列を使えばよいでしょう。 使う前に初期化を忘れずに。

課題２の提出物については、後ろをみてください。

データ構造: Queue (待ち行列)

データ構造としては、ある種のリストデータ構造で、 最後から要素を追加して、先頭から要素を取り出す、first in first out (FIFO) 用途です。

enqueue で要素追加、dequeueが要素取り出しです。ELEM は、適当な型に #define でもして使ってください。

typedef struct queue {
    int head, tail, size;
    ELEM buf[BUFSIZE];
} queue_t, * queue_tp;

/****
 * queue のサイズを返す
 * q: 対象 queue へのポインタ
 * 返り値: queue のサイズ
 */
int qSize(queue_tp q);
/****
 * queue への要素追加
 * q: 対象 queue へのポインタ
 * data: 追加をおこなう要素
 */
void enqueue(queue_tp q, ELEM data);
/****
 * queue からの要素取り出し
 * q: 対象 queue へのポインタ
 * 返り値: 取得要素
 */
ELEM dequeue(queue_tp q);

実装は、プログラムの方を見てもらえば良いですが、 ring buffer というのを使っています。

構造体を値として扱う

さて、先ほどの queue_t ですが、 今回は、関数の引数や返り値として、struct point (= point_t) を使います。 つまり、構造体を「値」として使うことになります。

関数呼び出しのときに、整数値やポインタを使う場合、当然、その値のコピーが渡されるのですが、構造体の場合も、コピーが作成されて引数もしくは返り値として使われます。 まあ、整数値のときと同じだと思ってもらえばOK です。

一方で、Queue の方は、 ポインタ型queue_tp を用いて管理されています。 当然ですよね？だって、コピーに要素積めたって、意味ないですから。 「本体」に要素追加するなら、ポインターをつかうしかないってわけです。

/****
 * queue への要素追加
 * q: 対象 queue へのポインタ
 * data: 追加をおこなう要素
 */
void enqueue(queue_tp 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_tp 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;
  }
}

課題２の提出物

課題２ですが、提出を２段階とします。BEEFから提出しましょう。

11/1 授業中に回答例を公開予定です（slackで公開予定)。

1. 解答プログラム例の公開までは、一般の提出となります。以下を提出してください。
   • プログラムファイル
   • レポート：学番＋氏名＋実行結果（debug 出力が混ざっていても構いません）
     • 課題２では、プログラム解説はなくて構いません。
     • アピールポイントがある人は、その旨解説入れてください。
2. 自力で解けなかった人は、正解例を参考にレポートを提出しましょう。
   • まず、未完成でも、その自作プログラムを提出すること。
   • 自分が作成できなかった部分がどの部分か、正解例ではどのように実現されていたか、解説すること（このあたりは、上記未完成プログラムの出来次第で変わるはず）
   • 正解プログラム例の実行を、デバッガなどでトレースし、正しく動作していることを説明すること。今回の例では、プログラム実行にしたがって、Queue がどのように状態を変化させていったのか、簡単なサンプル(sample の １つめ 2x3 の盤面のケース)を用いて説明すること。