# POJ-3126 Prime Path

2019/7/23 8:55:23 人评论 次浏览 分类：学习教程

F - Prime Path (POJ - 3126)

``````using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5+5;

bool isp[N] = {0};
bool vis[N] = {0};
int n, s, e;

struct P {
int x;
int step;
};

void euler() {
int p[N], m=0;
for(int i=2; i<=N; i++) {
if(!isp[i])
p[m++] = i;
for(int j=0; j<m; j++) {
if(p[j]*i>N)
break;
isp[p[j]*i] = 1;
if(i%p[j]==0)
break;
}
}
}

int bfs() {
memset(vis, 0, sizeof(vis));

P sp;
sp.x = s;
sp.step = 0;

queue<P> q;
q.push(sp);
vis[sp.x] = 1;

while(!q.empty()) {
P tp = q.front();
q.pop();

if(tp.x==e) {
return tp.step;
}
P np = tp;

for(int i=1; i<=9; i+=2) {
np.x = tp.x/10*10 + i;
if(np.x!=tp.x && !vis[np.x] && !isp[np.x]) {
np.step = tp.step+1;
q.push(np);
vis[np.x] = 1;
}
}
for(int i=0; i<=9; i++) {
np.x = tp.x/100*100 + i*10 + tp.x%10;
if(np.x!=tp.x && !vis[np.x] && !isp[np.x]) {
np.step = tp.step+1;
q.push(np);
vis[np.x] = 1;
}
}
for(int i=0; i<=9; i++) {
np.x = tp.x/1000*1000 + i*100 + tp.x%100;
if(np.x!=tp.x && !vis[np.x] && !isp[np.x]) {
np.step = tp.step+1;
q.push(np);
vis[np.x] = 1;
}
}
for(int i=1; i<=9; i++) {
np.x = i*1000 + tp.x%1000;
if(np.x!=tp.x && !vis[np.x] && !isp[np.x]) {
np.step = tp.step+1;
q.push(np);
vis[np.x] = 1;
}
}
}
return 0;
}

int main(void) {
euler();
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%d%d", &s, &e);
printf("%d\n", bfs());
}
return 0;
}

``````

暂无相关的资讯...

-->