HDU4474 Yet Another Multiple Problem BFS搜索

题意：给定一个数N(1<=N<=10000)，求N的一个最小的倍数能够被N整除。

解法：粗看起来题意简单，但是确无从下手，其实正确的解法就是通过搜索来搞定，由于N不太，因此N的余数类也不会很大，采用从小到大的枚举策略能够使得后面达到的同余类状态不及前面的优秀，这样就能够在非常短的时间内找到答案。

bfs过程中对于在状态与状态之间建立前驱指针，这样就能够输出最后的结果。

一个状态需要记录以下值：1.当前状态对N的余数；2.当前放置的数字；3.前驱指针。

状态之间的转移：mod' = (mod*10 + digit) % N

从1位开始依次枚举，然后扩大到2位，3位.....

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

int N, M;
char hav[15];
char vis[10005];

struct Node {
    int mod, f; // mod表示对N取余后的值，f表示父亲节点的编号
    char digit; // 当前放置的数字为多少 
}info, que[10005];

void show(int x) {
    if (que[x].f != -1) {
        show(que[x].f);
    }
    printf("%d", que[x].digit);
}

inline bool ok(int x, int &ans) {
    if (que[x].mod == 0) {
        ans = x;
        return true;
    }
    return false;
}

void bfs() {
    int ans, front = 0, tail = 0;
    bool finish = false;
    for (int i = 1; i < 10; ++i) { // staring from 1 
        if (!hav[i]) { // 如果这个数码没有被限制
            que[tail].mod = i % N;
            if (vis[que[tail].mod]) continue; // 判定这个余数是否已经走过 
            vis[que[tail].mod] = 1;
            que[tail].digit = i;
            que[tail].f = -1; // -1是一个特殊的标识，表示到了根节点
            // 把一个合法的初始化根节点加入到队列中去
            if (ok(tail, ans)) {
                finish = true;
                break;
            }
            ++tail;
        }
    }
    while (!finish && front != tail) {
        info = que[front++]; // 取出队首元素
        for (int i = 0; i < 10; ++i) {
            if (!hav[i]) {
                que[tail].mod = (info.mod * 10 + i)    % N;
                if (vis[que[tail].mod]) continue;
                vis[que[tail].mod] = 1;
                que[tail].digit = i;
                que[tail].f = front-1; // 保留上一个状态的编号
                if (ok(tail, ans)) {
                    finish = true;
                    break;
                }
                ++tail;
            }
        }
    }
    
    if (finish) {
        show(ans);
        puts("");
    } else {
        puts("-1");    
    }
}

int main() {
    int c, ca = 0;
    while (scanf("%d %d", &N, &M) != EOF) {
        memset(hav, 0, sizeof (hav));
        memset(vis, 0, sizeof (vis));
        for (int i = 0; i < M; ++i) {
            scanf("%d", &c);
            hav[c] = 1; // 标志为1的数字不能够使用    
        }
        printf("Case %d: ", ++ca);
        bfs();
    }
    return 0;    
}