poj1426

poj1426
bfs暴力

通过bfs搜索每个可能性，从1开始，通过使用110和110+1 来遍历最后一位为1或者0的所有情况；
使用stl的队列会超时，所以使用数组模拟队列。

#include <iostream>
#include <queue>
using namespace std;
#define maxn 10000000
long long q[maxn];
//queue<long long> q;
long long bfs(int n) {
    //queue<long long> q;
    int front = 0;
    int rear = 0;
    q[rear++] = 1;
    //q.push(1); // 从1开始暴力搜
    for(;;) {
        //long long f = q.front();
        long long f = q[front++];
        //q.pop();
        if(0 == f % n) return f;
        else {
            //q.push(f * 10); //最后一位0
            //q.push(f * 10 + 1); //最后一位1
            q[rear++] = f * 10;
            q[rear++] = f * 10 + 1;
        }
    }
    //return 0;
}


int main()
{
    int n;
    while(cin >> n && n)
        cout << bfs(n) <<endl;
    return 0;
}