プログラムの実行結果は以下の通り。
□21□3□ 23430□ 321254 □34□2□ □□□□□□ □□□□□□ max length: 5 pos [row:2][col:4]
問題文で言うとMの位置になる。
プログラムのソースは以下の通り。
#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", "0123456789"+(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; }