Problem Solving►UVa

UVa 910 - TV game

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給你一張圖，問從 A 點走到各特殊點的方法數。

Solution

e.g. A B C (A 可以到 B 或 C)
(走 (n+1) 步後到達 B 的方法數) 會包含(+=) (走 n 步到達 A 的方法數)
(走 (n+1) 步後到達 C 的方法數) 會包含(+=) (走 n 步到達 A 的方法數)

分別記錄 n 和 n - 1 時間點的狀態。
past: 上一時間點到各點的方法數
now: 目前到各點的方法數

最後把所有特殊點的方法數加總即是答案。

Code

UVa 910
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <new>
#define ORD(ch) (ch - 'A')
#define N 26

int main()
{
    int n;
    char input[10];
    int *past = new int[N](), *now = new int[N]();

    while (scanf("%d ", &n) != EOF)
    {
        int goal[N], gn = 0;
        int G[N][2];
        bool use[N] = {};
        for (int i = 0; i < n; ++i)
        {
            fgets(input, 10, stdin);
            use[ORD(input[0])] = true;
            G[ORD(input[0])][0] = ORD(input[2]);
            G[ORD(input[0])][1] = ORD(input[4]);
            if (input[6] == 'x')
                goal[gn++] = ORD(input[0]);
        }

        int m;
        scanf("%d", &m);
        
        memset(past, 0, sizeof(int) * N);
        past[0] = 1; //'A' is start point

        for (int i = 0; i < m; ++i) //step
        {
            for (int j = 0; j < N; ++j)
                if (use[j])
                {
                    now[G[j][0]] += past[j];
                    now[G[j][1]] += past[j];
                }

            //swap now and past, then initialize now
            int *tmp = past;
            past = now;
            now = tmp;
            memset(now, 0, sizeof(int) * N);
        }

        //加總所有的特殊點
        int ans = 0;
        for (int i = 0; i < gn; ++i)
            ans += past[goal[i]];

        printf("%d\n", ans);
    }

    delete[] past;
    delete[] now;
    return 0;
}