迷路(朝日新聞beパズル)2004年10月16日

難易度が★★★★★となっている迷路問題。難易度5は珍しいので久々に解いてみることにした。プログラムは迷路の一般的な解法プログラムを利用する。

STARTからGOALを目指す。途中案山子(かかし)を5体，米俵(こめだわら)を10俵通らなければならない。多くても少なくてもダメ。同じ所を2回以上通るのもダメ。途中の道にいた烏(カラス)の数は何匹か。

実際の新聞では目の部分は表示されています。

迷路問題の定石通り交差点に番号を振る。

今回は案山子と俵を記録する必要があるので，経路情報(P[ ][ ])にこれらを入れることを考える。

P[小さい数字][大きい数字]=案山子の数*10 + 俵の数;

但し，これだと経路はあるのに，以下のように

P[2][5] = 0;

となってしまうことがある。経路は0より大きな数にしたいので，以下のように経路がある場合100以上とする。

P[小さい数字][大きい数字]=100 + 案山子の数*10 + 俵の数;

カラスの数は経路が確定したら手で勘定する。プログラムで出力したい場合以下のようにカラスの数も入れてしまうことができる(プログラムはこちらを採用した)。

P[小さい数字][大きい数字]=1000 + カラスの数*100 + 案山子の数*10 + 俵の数;

途中P[ ][ ]データを作成していて，妙なことに気づいた。以下の箇所は経路情報を作成できない！

P[15][21] = 100 + 1*10 + 1;    
P[15][22] = 100 + 1*10 + 1;    
P[21][22] = 100 + 1*10 + 1;

ではダメなのである。うーん，暫く考えてしまった。結局以下のように新しい番号を振り，途中の案山子と俵の数を0と見なすことにした。

P[15][25] = 100 + 0*10 + 0;    
P[21][25] = 100 + 0*10 + 0;    
P[22][25] = 100 + 0*10 + 0;

そうすると25の位置にある案山子と俵はどこへ行ってしまうのか?

findGoal()で25地点を通過したらそれまでの案山子の数と俵の数に+1する。

プログラムは以下の通り。カラスの数も入れて作ってみた。肝となる部分を赤く表示した。

#include 
#include 

int s=1;
int g=20;
#define S 25
int P[S+1][S+1];
int once[S+1];
int visit[S+1];

void findGoal( int level, int p, int cntKarasu, int cntKakasi, int cntTawara)
{
  visit[level] = p;
  if( once[p]) return; // 一度通った地点
  if( p == 25) { cntKakasi += 1; cntTawara += 1;}
  if( cntKakasi > 5 || cntTawara > 10) return; // 案山子と俵のどちらか一方の数が問題をオーバーした
  if( p==g) {
    if( cntKakasi != 5 || cntTawara != 10) { return;} // ゴールまで到達したけど案山子と俵の数が問題を満たさない
    printf( "FindGoal : %d, %d\n", cntKakasi, cntTawara);
    for( int i=0; i<= level; i++) {
      printf( "%d ", visit[i]);
    }
    printf( "\n");
    printf( "カラス:%d匹\n", cntKarasu);
    return;
  }
  once[p] = 1;
  for( int next=1; next<= S; next++) { // pから到達可能な全ての地点を調べる
    if( !P[p][next]) {
      continue; // 到達出来ない地点は無視する
    }
    findGoal( level+1, next, cntKarasu+P[p][next]/100%10, cntKakasi+P[p][next]/10%10, cntTawara+P[p][next]%10);
  }
  once[p] = 0;
}

int main( int argc, const char* argv[])
{
  P[1][2]=1000+0*100+2*10+1;
  P[1][9]=1000+2*100+1*10+0;
  P[2][3]=1000+1*100+2*10+2;
  P[2][5]=1000+0*100+0*10+0;
  P[3][4]=1000+0*100+0*10+0;
  P[3][19]=1000+2*100+1*10+2;
  P[4][18]=1000+0*100+1*10+1;
  P[4][19]=1000+1*100+2*10+2;
  P[5][6]=1000+0*100+0*10+0;
  P[5][17]=1000+0*100+0*10+1;
  P[6][7]=1000+1*100+0*10+2;
  P[6][16]=1000+0*100+0*10+1;
  P[7][8]=1000+0*100+0*10+3;
  P[7][15]=1000+0*100+2*10+0;
  P[8][9]=1000+0*100+0*10+0;
  P[8][12]=1000+0*100+0*10+1;
  P[9][10]=1000+1*100+2*10+0;
  P[10][11]=1000+0*100+0*10+0;
  P[10][24]=1000+1*100+0*10+3;
  P[11][12]=1000+0*100+0*10+3;
  P[11][14]=1000+1*100+1*10+1;
  P[12][13]=1000+1*100+0*10+0;
  P[13][14]=1000+0*100+0*10+0;
  P[13][22]=1000+1*100+0*10+2;
  P[14][23]=1000+0*100+0*10+1;
  P[15][16]=1000+0*100+0*10+0;
  P[15][25]=1000+0*100+0*10+0;
  P[16][17]=1000+1*100+0*10+0;
  P[17][18]=1000+0*100+0*10+0;
  P[18][21]=1000+0*100+1*10+3;
  P[19][20]=1000+0*100+1*10+0;
  P[20][23]=1000+0*100+2*10+1;
  P[20][24]=1000+2*100+2*10+0;
  P[21][25]=1000+0*100+0*10+0;
  P[22][23]=1000+0*100+0*10+2;
  P[22][25]=1000+0*100+0*10+0;
  for( int i=0; i<= S; i++) for( int j=0; j<= S; j++) if( P[i][j]) P[j][i] = P[i][j];
  findGoal( 0, s, 0, 0, 0);
  return 0;
}

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

FindGoal : 5, 10
1 9 8 12 13 14 23 22 25 15 16 6 5 17 18 4 3 19 20 
カラス:5匹

図示すると経路は以下のようになる。経路上にいるカラスの数は5匹であることが判る。