UVA 910 TV game

dp uva dfs

我一開始看錯了題目, 以為是只有走 ‘1’ 的邊才把總值加一.
我是想到了用 dfs, 但是又怕時間太長, 結果看了別人才敢動手.
這一點真的要改一下.

uva910.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstring>

int dp[30][35];
int E[30][2];
int isEndPt[30];

int dfs(int position, int v) {
  if(v == 0) return isEndPt[position];

  if(dp[position][v] != -1) return dp[position][v];

  return (dp[position][v] = dfs(E[position][0], v - 1) + dfs(E[position][1], v - 1));
}

int ctoi(char c) {
  return c - 'A';
}

int main() {
  int n, m;
  char a, b, c, d;

  while(scanf("%d\n", &n) != EOF) {
    memset(dp, -1, sizeof(dp));
    memset(E, 0, sizeof(E));
    memset(isEndPt, 0, sizeof(isEndPt));

    for(int i = 0; i < n; ++i) {
      scanf("%c %c %c %c\n", &a, &b, &c, &d);
      E[ctoi(a)][0] = ctoi(b);
      E[ctoi(a)][1] = ctoi(c);
      isEndPt[ctoi(a)] = (d == 'x')?1:0 ;
    }

    scanf("%d\n", &m);
    printf("%d\n", dfs(0, m));
  }

  return 0;
}