素数路径Prime Path POJ-3126 素数,BFS
2024-09-01 04:58:10
题目链接:Prime Path
题目大意
从一个四位素数m开始,每次只允许变动一位数字使其变成另一个四位素数。求最终把m变成n所需的最少次数。
思路
BFS。搜索的时候,最低位为0,2,4,6,8可以先排除(偶数不会是素数),最高位是0的也可以排除。这个题判断素数的次数比较少,可以不打素数表。
题解
第二次写的时候代码写的很乱。。没有第一遍干净了
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; int num, m, n, ans;
int vis[];
int a[] = {,,,,,,,,,};
int digit[];
struct point
{
int val;
int step;
}p; void div(int x) //把数拆分
{
for(int i = ; i < ; i++)
{
digit[i] = x % ;
x = x/;
}
} bool isPrime(int n)
{
for(int i = ; i*i <= n; i++)
{
if(n % i == )
{
return false;
}
}
return true;
} int bfs(int m, int n)
{
queue<point> q;
p.val = m;
p.step = ;
q.push(p);
while(!q.empty())
{
point cur = q.front();
if(cur.val == n)
{
return cur.step;
}
//cout << cur.val << " ";
vis[cur.val] = ;
div(cur.val);
for(int i = ; i < ; i++)
{
if(i == digit[] || i == || i == || i == || i == ) continue;
int x = digit[]* + digit[]* + digit[]* + i;
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = digit[]* + digit[]* + i* + digit[];
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
} for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = digit[]* + i* + digit[]* + digit[];
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = i* + digit[]* + digit[]* + digit[];
if(vis[x]|| !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
q.pop();
}
return -; //没有找到
} int main(int argc, char const *argv[])
{
#ifdef debug
freopen("test.txt","r",stdin);
#endif
cin >> num;
while(num--)
{
memset(vis, ,sizeof(vis));
cin >> m >> n;
ans = bfs(m, n);
if (ans == -)
{
cout << "Impossible" << endl;
continue;
}
cout << ans << endl;
}
}
最新文章
- 解决:IntelliJ IDEA 编译错误,提示 Compilation failed: internal java compiler error
- Intelij IDEA 2016.3安装mybatis插件并激活教程
- Furatto – 轻量,友好的响应式前端开发框架
- Allegro笔记三
- 利用matlab编写实现显示fmri切片slice图像 混合显示 不同侧面显示 可叠加t检验图显示 by DR. Rajeev Raizada
- [AngularJS] angular-formly: expressionProperties
- 【PAT】1035. Password (20)
- tcpdump使用方法小结
- php通过system()调用Linux命令问题
- 一天就学会Android开发四大组件
- Java中泛型数组创建总结
- SpringBoot+Dubbo+Zookeeper整合搭建简单的分布式应用
- windows查看笔记本电池使用报告
- [转] React之Immutable学习记录
- 2018-04-21 搭建Python官方文档翻译环境
- transient关键字详解
- url的反向解析
- Hibernate学习笔记2.4(Hibernate的Id生成策略)
- python转换html到pdf文件
- 20155214 2016-2017-2 《Java程序设计》第10周学习总结