プログラムの実行結果は以下の通り。
□２１□３□ ２３４３０□ ３２１２５４ □３４□２□ □□□□□□ □□□□□□ max length: 5 pos [row:2][col:4]
問題文で言うとＭの位置になる。
プログラムのソースは以下の通り。
#include "puzutl.h"
int cost[6][6]; // 何歩で到達したか
int mat[6][6] = { // 到達可能点
{ 0, 1, 1, 0, 1, 0},
{ 1, 1, 1, 1, 1, 0},
{ 1, 1, 1, 1, 1, 1},
{ 0, 1, 1, 0, 1, 0},
{ 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0},
};
YesNo get_direction( int row, int col, int direction, int& new_row, int& new_col)
{
if( direction == 0) { new_row = row-2; new_col = col-1; }
else if( direction == 1) { new_row = row-1; new_col = col-2; }
else if( direction == 2) { new_row = row+1; new_col = col-2; }
else if( direction == 3) { new_row = row+2; new_col = col-1; }
else if( direction == 4) { new_row = row+2; new_col = col+1; }
else if( direction == 5) { new_row = row+1; new_col = col+2; }
else if( direction == 6) { new_row = row-1; new_col = col+2; }
else if( direction == 7) { new_row = row-2; new_col = col+1; }
else pe( "ProgramError\n");
if( new_row < 0 || new_row >= 6) return NO;
if( new_col < 0 || new_col >= 6) return NO;
if( mat[new_row][new_col]) return YES;
return NO;
}
void visit( int level, int row, int col)
{
if( mat[row][col] == 0) return; // ここは来ることが出来ない
if( cost[row][col] && level >= cost[row][col]) return; // 既に訪問したし，以前の方が短い歩数で訪問できた
cost[row][col] = level;
int new_row, new_col;
for( int i=0; i< 8; i++) { // 8方向を全て調べる
if( get_direction( row, col, i, new_row, new_col)) visit( level+1, new_row, new_col);
}
}
int main( int argc, cstring argv[])
{
// 全ての地点の歩数を計算し，
visit( 1, 1, 4);
// 最大のものを求めて出力する
int row, col;
int m = -1, v;
int row_long = -1, col_long = -1;
for( row=0; row< 6; row++) {
for( col=0; col< 6; col++) {
v = cost[row][col];
if( v == 0) ps( "□"); else ps( "%-.2s", "０１２３４５６７８９"+(v-1)*2);
if( v >= m) {
m = v;
row_long = row; col_long = col;
}
}
ps( "\n");
}
ps( "max length: %d\n", m-1);
ps( "pos [row:%d][col:%d]\n", row_long, col_long);
return 0;
}