Problem Solving►UVa

UVa 11730 - Number Transformation

Contents

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

Problem

題目網址
中文網址

Solution

注意可以加的數字不包含 1 和 自己。
對每個可能性做 BFS ，邊記錄每個節點的深度(轉換次數)。

已經將某數字排進去後，後面再遇到同樣的數字不需要再做一次，深度一定大於等於前面做過的。

Code

UVa 11730UVa 11730 - Number Transformation
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
62
63
64
65
#include<cstdio>
#include<queue>
#define N 1001
using namespace std;

int prime[N];
int bfs(int s, int t);
int main()
{
    //建質數表
    bool notPrime[N] = { true, true };
    int s, t, i, j;
    for (i = 2; i <= 32; i++)
        for (j = i + i; j < N; j += i)
            notPrime[j] = true;
    int cp = 0;
    for (i = 2; i < N; i++)
        if (!notPrime[i])
            prime[cp++] = i;

    int Case = 0;
    while (scanf("%d%d", &s, &t) && s&&t)
    {
        printf("Case %d: ",++Case);
        if (s == t)
            puts("0");
        else
            printf("%d\n", bfs(s,t));
    }

    return 0;
}
int bfs(int s, int t)
{
    int count[1001] = {};//深度
    queue<int> q;
    q.push(s);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int p_idx = 0; prime[p_idx] < now; p_idx++)//不包含 now 自己
        {
            if (!(now%prime[p_idx]))
            {
                int temp = now + prime[p_idx];
                if (count[temp])//已經排進去過了
                    continue;

                if (temp == t)
                    return count[now] + 1;
                else if (temp < t)
                {
                    count[temp] = count[now]+1;
                    q.push(temp);
                }
                else
                    break;
            }
        }
    }

    return -1;
}