您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-1426 Find The Multiple

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-1426 Find The Multiple
DFS
输出能被n整除且仅由(0|1)组成的数任意一个
普通

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <queue>
#include <math.h>

using namespace std;

const int maxn = 1e5+10;

int t;
int n, m;
int d[maxn];
int vst[maxn];

bool isPrime(int x){
    for(int i = 2; i < sqrt(x)+1; ++i)
        if(x % i == 0)
            return false;
    return true;
}

int f(int a[], int x){
    int sum = 0;
    for(int k = 0; k < 4; ++k){
        sum *= 10;
        sum += a[k];
    }
    return sum;
}

void bfs(){
    queue<int> q;
    q.push(n);
    vst[n] = 1;
    while(!q.empty()){
        int p = q.front();
        q.pop();
        if(p == m){
            printf("%d\n", d[p]);
            return;
        }
        int a[4];
        int tmp = p;
        for(int i = 0; i < 4; ++i){
            a[4-i-1] = tmp%10;
            tmp /= 10;
        }
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 10; ++j){
                if(!i && !j)
                    continue;
                tmp = a[i];
                a[i] = j;
                int next = f(a, 4);
                if(!vst[next] && isPrime(next)){
                    q.push(next);
                    vst[next] = 1;
                    d[next] = d[p] + 1;
                }
                a[i] = tmp;
            }
        }
    }
}

int main(){
    scanf("%d", &t);
    while(t--){
        memset(d, 0, sizeof(d));
        memset(vst, 0, sizeof(vst));
        scanf("%d%d", &n, &m);
        bfs();
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ-3279 Fliptile

下一篇:POJ-3126 Prime Path

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00