パズル万華鏡

面白いパズルの紹介と解説をします。

最短コース問題・考察

 すべての最短コースを列挙するプログラムを示します。

#include <stdio.h>
#include <stdlib.h>
#define N 40 /* 町のサイズnの最大値。*/
int count,   /* 最短経路数。*/
    n;       /* nの値。*/
char path[2*N+1]; /* 経路を表現する配列。                      
                    path[i]はi番目の進行方向(R,D)を意味する。*/
void node(int i, int j);

int main() {

  /* nの読み込み。*/
  scanf("%d",&n); 
  if( (n <= 0)||(n > N) ) { exit(0); }

  /* 初期設定。*/
  count = 0;

  /* バックトラック。*/
  node(0,0);

  /* 結果の表示。*/
  printf("n=%d count=%d\n",n,count);
}

/* i:交差点右方向座標、j:交差点下方向座標。
   交差点(i,j)への移動を調べる。*/
void node(int i, int j) {
  int k;

  /* 条件を満たさない場合、戻る。*/ 
  if( (i > n)||( j > n)||(j < i) ) { return; }

  if( i+j == 2*n ) {
    /* 最短コースの表示。*/
    count++; printf("[%d] ",count);
    path[2*n] = '\0';
    printf("%s\n",path);
    return;
  } 
 
  /* 下方向へ移動。*/
  path[i+j] = 'D';
  node(i+1,j);
  /* 右方向へ移動。*/        
  path[i+j] = 'R'; 
  node(i,j+1);
}

実行結果
% ./a.out
2
[1] RDRD
[2] RRDD
n=2 count=2
% ./a.out
3
[1] RDRDRD
[2] RDRRDD
[3] RRDDRD
[4] RRDRDD
[5] RRRDDD
n=3 count=5
% ./a.out
4
[1] RDRDRDRD
[2] RDRDRRDD
[3] RDRRDDRD
[4] RDRRDRDD
[5] RDRRRDDD
[6] RRDDRDRD
[7] RRDDRRDD
[8] RRDRDDRD
[9] RRDRDRDD
[10] RRDRRDDD
[11] RRRDDDRD
[12] RRRDDRDD
[13] RRRDRDDD
[14] RRRRDDDD
n=4 count=14
f:id:isemba:20180405103316j:plain