jsp reactjs sorting d3 Semantic UI Uploadify Momentjs bootstrap后台管理系统 java商城源码 jquery获取元素 css获取最后一个元素 mysql批量更新数据 python开发安卓应用 hbuilder插件 python加注释 python课程 java编程 java删除数组中的元素 java学习基础 java字符串匹配 javaenum java怎么输出数组 java中long java定义字符串 linux装机 matlab2016a安装教程 端口关闭工具 vbs编程教学 为什么英雄联盟无法连接服务器 god2iso 桌面数字时钟 有线网卡驱动下载 mac版matlab linux系统下载 Mapper 文件压缩工具 dnf风神加点 华为工具箱 小米主题编辑器 联想7450加粉清零
当前位置: 首页 > 学习教程  > 编程语言

2021-02-13 poj 3126 Prime Path

2021/2/13 19:16:28 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

BFS 1.把四位数的个&#xff0c;十&#xff0c;百&#xff0c;千位分别拿出来&#xff0c;改过一个数后再加回去。 2.判断素数是小于等于sqrt&#xff08;n&#xff09;&#xff0c;例如9&#xff0c;如果没有判断过它的平方根&#xff0c;他就被认为是素数了。 #include<…

BFS

1.把四位数的个,十,百,千位分别拿出来,改过一个数后再加回去。
2.判断素数是小于等于sqrt(n),例如9,如果没有判断过它的平方根,他就被认为是素数了。

#include<iostream> 
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
int Prime[10000];
int vis[10000];
struct node{
	int x, step;
};
void init(){
	int i, j;
	for(i=1000; i<10000; ++i){
		for(j=2; j<=sqrt(i); ++j){
			if(i%j == 0) break;
		}
		if(j > sqrt(i)) Prime[i] = 1;
		else Prime[i] = 0;
	}
}
int BFS(int a, int b){
	node now, next;
	queue <node> q;
	while(!q.empty()) q.pop();
	now.x = a; now.step = 0;
	q.push(now);
	vis[now.x] = 1;
	while(!q.empty()){
		now = q.front();
		if (now.x == b) return now.step;
		q.pop();
		int t[5];
		t[1] = now.x/1000;
		t[2] = now.x%1000/100;
		t[3] = now.x%100/10;
		t[4] = now.x%10;
		for(int j=0; j<=9; ++j){
			for(int i=1; i<=4; ++i){
		    	if (t[i] == j) continue;
		    	if(i == 0 && j == 0) continue;
		    	if (i == 1) next.x = j*1000+t[2]*100+t[3]*10+t[4];
		    	if (i == 2) next.x = t[1]*1000+j*100+t[3]*10+t[4];
				if (i == 3) next.x = t[1]*1000+t[2]*100+j*10+t[4];
		    	if (i == 4) next.x = t[1]*1000+t[2]*100+t[3]*10+j;
		    	if (Prime[next.x] && !vis[next.x]){
		    		vis[next.x] = 1;
		    		next.step = now.step+1;
		    		q.push(next);
				}
			}
		}
	} 
	return -1;
}
int main(){
	int n;
	int a, b;
	init();
	cin >> n;
	while(n--){
		cin >> a >> b;
		memset(vis, 0, sizeof(vis));
		int num = BFS(a, b);
		if(num != -1) cout << num << endl;
		else cout << "Impossible" << endl;
	}
} 

本文链接: http://www.dtmao.cc/news_show_700306.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?