C/C++の宿題を片付けます 90代目
■ このスレッドは過去ログ倉庫に格納されています
0604デフォルトの名無しさん
2007/06/21(木) 17:40:22ありがとうございます〜
もう一問ありました(汗)
問題は一緒なのですが・・
[1] 授業単元:待ち行列
[2] 問題文(含コード&リンク):
N 人の人がいて,それらは番号 0, 1, 2, ..., N-1 で表されているとする。
この N 人の人間関係(知り合いかどうか)を表した配列 a[N][N] がある。
ただし, i 番目の人と j 番目の人とが知り合いであるとき a[i][j] == a[j][i] == 1 であり,知り合いでないとき a[i][j] == a[j][i] == 0 である。
このとき, x 番目の人から,知り合いの知り合いの知り合い.... という繋がりで, y 番目の人まで辿り着くには,最小で何回の知り合いという関係が必要か,を返す関数 int acquaintDistance(int a[N][N], int x, int y) を作れ。
なお,x 番目の人から y 番目の人に辿り着けない場合には,acquaintDistance は -1 を返すこととする。
関数名の acquaint は知り合いにさせる, distance は距離という意味である。
ヒント:待ち行列を利用する。最初に x を待ち行列に入れ,
後は,「待ち列から一つ dequeue して,その人の知り合いを待ち行列に enqueue する」
ということを繰り返す。ただし,一度 enqueue した人は二度と enqueue しないようにし, y を enqueue する時点あるいは enqueue する一がいなくなった時点で,終了する。
x から各人までの知り合い距離を入れる配列も用意しておき,新しい人を enqueue する度に,その人までの距離をその配列に入れる。
[3] 環境
[3.1] OS:Vine LINUX
[3.2] コンパイラ名とバージョン:gcc
[3.3] 言語:C
[4] 期限:2007年6月28日10時45分まで
[5] その他の制限:こちらも、どうかよろしくお願いします。
■ このスレッドは過去ログ倉庫に格納されています