プログラムの実行結果は以下の通り。'*'を伴う位置が移動後立ち止まる位置になる。
Find 歩数:34 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 13 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:36 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 13 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:38 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 13 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:36 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 13 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:38 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 13 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:38 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 18 14 13 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:40 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 18 14 13 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 18 14 13 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:40 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 18 14 13 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 18 14 13 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 23 22 21 20* 17 10 11 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:44 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 23 22 21 20* 17 10 11 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:46 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 23 22 21 20* 17 10 11 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:44 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 23 22 21 20* 17 10 11 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:46 経路:0* 1 2* 3 4* 5 6* 9 16* 15 14 18 24* 23 22 21 20* 17 10 11 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:38 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 18 14 13 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:40 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 18 14 13 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 18 14 13 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:40 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 18 14 13 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 18 14 13 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:42 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 23 22 21 20* 17 10 11 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:44 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 23 22 21 20* 17 10 11 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:46 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 23 22 21 20* 17 10 11 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:44 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 23 22 21 20* 17 10 11 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:46 経路:0* 1 2* 3 4* 5 6* 9 16* 19 26 25 24* 23 22 21 20* 17 10 11 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:26 経路:0* 1 2* 8 12* 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:28 経路:0* 1 2* 8 12* 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:30 経路:0* 1 2* 8 12* 11* 12 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:28 経路:0* 1 2* 8 12* 13* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:30 経路:0* 1 2* 8 12* 13* 12 11* 12 8* 12 11 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 Find 歩数:20 経路:0* 7 10* 7 0 1* 2 3* 4 5 6 9* 16 19* 26 25 24 23* 24 25 31 件見つけた
最後に出力された歩数20が最短の経路になっている。但し問題では最短経路を求めるとは書いていない。
最短経路を図にすると以下の通り。
それ以外の経路は10番の升に合流後，同じ経路になる。
プログラムのソースは以下の通り。
#include "puzutl.h"
const int N = 27; // 位置の数
int dist[N] = { 2,2,2,4,2,3,2,3,3,2,3,2,1,2,2,1,4,3,1,4,4,1,2,3,4,1,0}; // 位置間の距離
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"
"...........................";
int visit[N]; // 訪問したか?
int route[1000]; // 経路情報
int num_find; // ゴールまでの道が何件見つかったか
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++;
ps( "Find 歩数:%d 経路:", level);
for( int i=0; i< level; i++) {
ps( "%d%s ", route[i]%N, (route[i]>=N)?"*":"");
}
ps( "\n");
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; // 訪問した事実を取り消す
}
}
int main( int argc, cstring argv[])
{
//--------------------------------------------------------------------
// まず接続状態を作成する。
//--------------------------------------------------------------------
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++;
}
}
//--------------------------------------------------------------------
// 後は接続状態に従って検索する。
//--------------------------------------------------------------------
find( 0/*level*/, 0/*残り歩数*/, 0/*開始位置*/, -1/*直前の位置*/);
ps( "%d 件見つけた\n", num_find);
return 0;
}