一段关于路径搜索的题目

帮WK做的题，Memo一下。

長さnの文字列を、m個のノードで構成されるグラフを探索し、以下のルールで文字列を生成する時、生成される文字列のパターン数を求めてください。
(1 <= m, n <= 20)

グラフのルール：
２個以上の複数のノードがある
各ノードは、a,b,c三つのアクションにより、他のノードに遷移する。
各ノードのa,b,cのアクションは、自分自身への遷移となる場合もある。

文字列生成のルール：
スタートノードから始まり、n回アクションをたどりノードを遷移し、n回目にゴールノードにたどり着くようにする。
その際のアクションの履歴により文字列を生成する（例：abaabcbca）
1番目のノードがスタートノード、番号の最も大きなノードがゴールノード。

例えば、添付された画像ファイルのようなグラフが与えられ、n=4と指定された場合は、
a b a c
a a a c
a c a c
a c b c
上記4つが生成されるので、解は4となります。

グラフ構造は、下記のようなフォーマットの配列で渡すように実装してください。
{
1(ノード番号), aのジャンプ先ノード番号, bのジャンプ先ノード番号, cのジャンプ先ノード番号,
2(ノード番号), aのジャンプ先ノード番号, bのジャンプ先ノード番号, cのジャンプ先ノード番号,
.....
}

例(C言語)：
#include <stdio.h>
#include <stdlib.h>

int graph1[16] = {
1, 2, 3, 3,
2, 2, 1, 4,
3, 3, 3, 3,
4, 1, 2, 2
};

int graph2[32] = {
1, 2, 3, 4,
2, 1, 5, 6,
3, 1, 5, 7,
4, 1, 6, 7,
5, 2, 3, 8,
6, 2, 4, 8,
7, 3, 4, 8,
8, 5, 6, 7
};

int graph3[16] = {
1, 2, 3, 3,
2, 2, 1, 2,
3, 3, 1, 3,
4, 1, 2, 2
};

//ここを実装する
int solve(int graph[], int n, int m){
return 0;
}

int main(void){
printf("%d\n", solve(graph1, 4, 4)); //4
printf("%d\n", solve(graph2, 9, 8)); //4920
printf("%d\n", solve(graph3, 19, 4)); //0
return 0;
}

以下是解答：

------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

int graph1[16] = {
1, 2, 3, 3,
2, 2, 1, 4,
3, 3, 3, 3,
4, 2, 2, 2
};

int graph2[32] = {
1, 2, 3, 4,
2, 1, 5, 6,
3, 1, 5, 7,
4, 1, 6, 7,
5, 2, 3, 8,
6, 2, 4, 8,
7, 3, 4, 8,
8, 5, 6, 7
};

int graph3[16] = {
1, 2, 3, 3,
2, 2, 1, 2,
3, 3, 1, 3,
4, 1, 2, 2
};

//ここを実装する

#define ACTION_NUM 3
#define ARRAY_COL (ACTION_NUM + 1)

static int g_count = 0;

void search_dst(int graph[], int n, int m, int num)
{
int i, row, pos;

for(row = 0; row < m; row++) {
   for(i = 1; i <= ACTION_NUM; i++) {
    pos = row * ARRAY_COL + i;

    if(graph[pos] == num) {
     if(n > 1) {
      search_dst(graph, n - 1, m, row+1);
     } else {
      if(row == 0) {
       g_count++;
      }
     }
    }
   }
}
}