すべての最短コースを列挙するプログラムを示します。
#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