【dfs/bfs+记录路径】Transformation: from A to B

逃离我推掉我的手 2022-06-05 10:49 152阅读 0赞

Think:  
1知识点：dfs/bfs+记录路径  
2题意：输入两个数a,b，询问通过两种操作是否可以由a得到b  
操作1:a = a\*2  
操作2:a = a\*10 + 1

[vjudge题目链接][vjudge]

以下为Accepted代码——bfs+记录路径

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    struct Node{
        LL num;
        int size;
    }link[104014];
    
    int op, tp;
    int pre[104014];
    
    void bfs(LL a, LL b);
    void pri_path(int id);
    
    int main(){
        LL a, b;
        while(~scanf("%lld %lld", &a, &b)){
            if(a == b){
                printf("YES\n");
                printf("1\n");
                printf("%lld\n", a);
            }
            else bfs(a, b);
        }
        return 0;
    }
    void bfs(LL a, LL b){
        int id = -1;
        Node t, tmp;
    
        op = tp = 0;
        memset(pre, -1, sizeof(pre));
        link[tp].num = a, link[tp].size = 1;
        tp++;
    
        while(op < tp){
            t = link[op++];
            tmp.num = t.num << 1;
            tmp.size = t.size + 1;
            if(tmp.num < b){
                link[tp++] = tmp;
                pre[tp-1] = op-1;
            }
            else if(tmp.num == b){
                link[tp++] = tmp;
                pre[tp-1] = op-1;
                id = tp-1;
                break;
            }
    
            tmp.num = t.num * (LL)10 + (LL)1;
            tmp.size = t.size + 1;
            if(tmp.num < b){
                link[tp++] = tmp;
                pre[tp-1] = op-1;
            }
            else if(tmp.num == b){
                link[tp++] = tmp;
                pre[tp-1] = op-1;
                id = tp-1;
                break;
            }
        }
        if(id == -1) {
            printf("NO\n");
        }
        else {
            printf("YES\n");
            printf("%d\n", link[id].size);
            pri_path(id);
            printf("\n");
        }
        return;
    }
    void pri_path(int id){
        if(pre[id] != -1)
            pri_path(pre[id]);
        if(pre[id] == -1) printf("%lld", link[id].num);
        else printf(" %lld", link[id].num);
    }

以下为Accepted代码——dfs

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    bool flag;
    LL a, b;
    int tp;
    LL link[1014];
    
    void dfs(LL x);
    
    int main(){
        while(~scanf("%lld %lld", &a, &b)){
            tp = 0, flag = false;
            link[tp++] = a;
            dfs(a);
            if(flag) {
                printf("YES\n");
                printf("%d\n", tp);
                for(int i = 0; i < tp; i++)
                    printf("%lld%c", link[i], i == tp-1? '\n': ' ');
            }
            else {
                printf("NO\n");
            }
        }
        return 0;
    }
    void dfs(LL x){
        if(flag || x > b) return;
    
        link[tp++] = x<<1;
        if(link[tp-1] == b){
            flag = true;
            return;
        }
        dfs(link[tp-1]);
        if(flag) return;
        else tp--;
    
        link[tp++] = x*(LL)10 + (LL)1;
        if(link[tp-1] == b){
            flag = true;
            return;
        }
        dfs(link[tp-1]);
        if(flag) return;
        else tp--;
    
        return;
    }

[vjudge]: https://vjudge.net/contest/200592#problem/A