POJ3126 Prime Path
POJ3126 Prime Path
题意：只能通过素数到达想要的那个数，问你最短的路径；
解题思路：拥有所有素数，bfs
复盘过程：虽然是个基本的bfs的题，但想用dfs做，本来想借助dfs搞清楚他的迭代过程，结果搜索的分支十分混乱，不对，应该说迭代的太深了，想想dfs先序遍历的原理就知道不能如此，于是最后向bfs低头。明显基础题。。基础不牢，地动山摇！
#include<stdio.h>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e4;
int vis[maxn],v[maxn];
int st,ans;
void prime(int n){
for(int i=2;i<=n;i++){
if(v[i])continue;
for(int j=i;j<=n/i;j++)v[i*j]=1;
}
}
int bfs(int st){
queue<pair<int,int> >q;
memset(vis,0,sizeof vis);
q.push({st,0});
vis[st]=1;
while(q.size()){
int fst=q.front().first;
int d=q.front().second;
if(fst==ans){
// cout<<d<<endl<<endl;
return d;
}
q.pop();
int a[4];int b[4];
a[0]=fst/1000,a[1]=(fst/100)%10,a[2]=(fst/10)%10,a[3]=fst%10;
for(int i=1;i<=9;i++){
for(int j=0;j<4;j++)b[j]=a[j];
b[0]=i;
int temp=b[0]*1000+b[1]*100+b[2]*10+b[3];
if(v[temp]||vis[temp])continue;
// cout<<temp<<" "<<d<<endl;
vis[temp]=1;
q.push({temp,d+1});
}
for(int i=0;i<=9;i++){
for(int j=0;j<4;j++)b[j]=a[j];
b[1]=i;
int temp=b[0]*1000+b[1]*100+b[2]*10+b[3];
if(v[temp]||vis[temp])continue;
vis[temp]=1;
// cout<<temp<<" "<<d<<endl;
q.push({temp,d+1});
}
for(int i=0;i<=9;i++){
for(int j=0;j<4;j++)b[j]=a[j];
b[2]=i;int temp=b[0]*1000+b[1]*100+b[2]*10+b[3];
if(v[temp]||vis[temp])continue;
vis[temp]=1;
// cout<<temp<<" "<<d<<endl;
q.push({temp,d+1});
}
for(int i=1;i<=9;i++){
for(int j=0;j<4;j++)b[j]=a[j];
b[3]=i;
int temp=b[0]*1000+b[1]*100+b[2]*10+b[3];
if(v[temp]||vis[temp])continue;
vis[temp]=1;
// cout<<temp<<" "<<d<<endl;
q.push({temp,d+1});
}
}
return -1;
}
int main()
{
int _;
cin>>_;
prime(10000);
while(_--)
{
cin>>st>>ans;
int sum=bfs(st);
if(sum==-1)cout<<"Impossible\n";
else cout<<sum<<endl;
}
return 0;
}
OPPO公司福利 1101人发布
而且一股AI味，AI简历的一个特点就是废话很多，一个点能分成四个点来讲，可以仔细优化一下。
btw，手机看简历不好看出来，可以把电脑上的简历截图放出来。