朝日新聞2006年4月7日パズル横丁解答

プログラムの実行結果は以下の通り。

□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;
}