以下のような図がある。スタートから升に書いてある歩数(升の数)だけ進みゴールに辿り着くにはどうすれば良いか。
Uターンは禁止。但し歩数分進んで止まったところでのUターンは可能。
プログラムは簡単だけど，データを作るのが面倒な問題。
まずは以下のように各位置に番号を振り配列で状態遷移図を作成できるようにする。
これを状態遷移図(MATRIX)にすると以下のようになる。赤い部分が移動可能な位置。
これをYesNoの配列で表現すると以下のように表現できる。赤い部分が移動可能でYES，白い部分が移動不可でNOになる。
const int N = 27; // 位置の数 YesNo connect[N][N]; // 接続状態
実際のデータを設定するには対角線より上の部分だけを示す以下のような文字列を作成し，プログラムでそれを展開する。
cstring conn = /* 接続状態(小さい数字⇒大きい数字のみ記載)
012345678901234567890123456*/
".X.....X..................."
"..X........................"
"...X....X.................."
"....X......................"
".....X....................."
"......X...................."
".........X................."
"..........X................"
"............X.............."
"................X.........."
"...........X.....X........."
"............X.............."
".............X............."
"..............X............"
"...............X..X........"
"................X.........."
"...................X......."
"....................X......"
"........................X.."
"..........................X"
".....................X....."
"......................X...."
".......................X..."
"........................X.."
".........................X."
"..........................X"
"...........................";
//--------------------------------------------------------------------
// まず接続状態を作成する。
//--------------------------------------------------------------------
cstring p = conn;
for( int row=0; row< N; row++) {
for( int col=0; col< N; col++) {
if( *p == 'X') {
connect[row][col] = 1;
connect[col][row] = 1; // 遷移図は対角線に対して対称なので
}
p++;
}
}
後はこれを以下のような再帰関数で検索する。
void find( int level, int rem, int pos, int prev_pos)
// level :I:探索の深さ
// rem :I:残り歩数(0になるまで止まらない)
// pos :I:位置
// prev_pos :I:直前の位置(Uターン禁止なので直前の位置が判る必要がある)
{
assert( level < 1000);
route[level] = pos; // 経路情報を記録
if( rem == 0) route[level] += N; // ちょうど立ち止まったところだけを判るようにしておく
int next_rem = rem-1; // 次のfind()の引数として使う歩数
if( rem == 0) { // ちょうど止まる場所か?
if( dist[pos] == 0) { // ゴールか?
num_find++;
発見
return;
}
if( visit[pos]) { // 既に訪れているか?
return; // 訪れているので先へ進めない
}
visit[pos] = level+1; // ここを訪問したとして記録しておく(>0を訪問済みとするため+1している)
next_rem = dist[pos]-1; // 升に書いてある歩数を歩く。再出発。
prev_pos = -1; // 一旦停止すれば元に戻れる
}
// 次の訪問候補値を探す
for( int i=0; i< N; i++) {
if( connect[pos][i] && // 次の場所へ行けるか?
i != prev_pos) { // 一つ前の場所ではない(Uターン禁止)
find( level+1, next_rem, i, pos); // 次の位置を調べる
}
}
if( rem == 0) { // ちょうど止まった場所だったので
visit[pos] = 0; // 訪問した事実を取り消す
}
}
答えは31件見つかりました。30件は，途中から最短経路の1件に合流するが答えとしては別扱いになる。
問題には「最短の経路」とは書いていないなー。
気象庁は津波情報を見直すべきじゃないかな。水曜日に千島列島沖で起きた地震で津波警報が大規模に出されていたけど，避難した人が少なすぎるという話だ。
注意報と警報だけだと余りに大雑把ではないか。気象庁のホームページを見ると警報にはさらに「大津波」と「津波」の2種類があるが，これでも少ないという印象だ。
警報が出て人が死に，何故警報が出たのに避難しなかったか議論されるまで改善されないんだろうなー。
津波も地域ごとの確率予報に切り替えるべきじゃないか。
「オオカミが来たー」って言っても3回目には効果無し。
解速度
即