hdu 4474

//因为n是小于等于10000可以利用这点进行搜索对n取余则余数为零时就为所找的。因为他的余数肯定小于10000所以不会无休止下去

#include<stdio.h>

#include<string.h>

#include<queue>

#include<iostream>

#include<algorithm>

#define N 1111111

using namespace std;

int pre[N],now[N],a[20];

void find(int k) {

if(pre[k]!=-1)

find(pre[k]);

printf("%d",now[k]);

}

void bfs(int n) {

int cur,i,j,k,next;

queue<int>q;

for(i=1;i<=9;i++)//判断1位数的情况

if(a[i]==0) {

k=i%n;

if(k==0) {

printf("%d\n",i);

return ;

}

if(pre[i]==0) {

pre[i]=-1;

now[i]=i;

q.push(i);

}

}

while(!q.empty()) {

cur=q.front();

q.pop();

for(i=0;i<=9;i++)

if(a[i]==0) {

next=cur*10+i;

k=next%n;

if(k==0) {

find(cur);

printf("%d\n",i);

return ;

}

if(pre[k]==0) {//控制如口如果出现过就肯定不是最小的因为最小的已经加进去过了

pre[k]=cur;//k

now[k]=i;//k

q.push(k);//k的个数是有限的不能用next可能会越界，越界的可能是禁止加入得数组成的数有一些你必须到很大才能遍历完1-10000

}

}

}

printf("-1\n");

}

int main() {

int n,m,i,j,count=0;

while(scanf("%d%d",&n,&m)!=EOF) {

memset(a,0,sizeof(a));

memset(pre,0,sizeof(pre));

for(i=1;i<=m;i++) {

scanf("%d",&j);

a[j]=1;

}

printf("Case %d: ",++count);

bfs(n);

}

return 0;

}

巴特西

hdu 4474

最新文章

热门文章