[백준 1936] 소수 경로

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

 

요구사항

최소 이동으로 n에서 m으로 변경

 

풀이

1. 4자리 수 소수 구한다

2. 한 자리씩 이동하면서 bfs로 최소이동 횟수 구한다

 

#include<iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <string.h>
//#include <windows.h>
//#include <map>
using namespace std;

struct go{
    int x;
    int cnt;
};
int n;
int map[10000];
int visit[10000];
int startv,endv;
int ans=0;
void solve(){
    queue<go> q;
    q.push({startv,0});
    visit[startv]=1;
    while(!q.empty()){
        int now = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
        //cout<<now<<endl;
        if(now==endv){
            ans=cnt;
            return;
        }
        int f = now / 1000;
        int s = now / 100;
        s = s%10;
        int t = now % 100;
        t = t/10;
        int fo = now%10;
        //1000부터
        for(int i=1 ; i<=9 ; i++){
            int nf=i*1000;
            int newnum= nf+s*100 + t*10 +fo;
          //  cout<<"nuw"<<newnum<<endl;
            if(visit[newnum]==0){
                visit[newnum]=1;
                q.push({newnum,cnt+1});
            }
        }
        //100
        for(int i=0 ; i<=9 ; i++){
            int nf=i*100;
            int newnum= f*1000 + nf+ t*10 +fo;
           // cout<<"nuw"<<newnum<<endl;
            if(visit[newnum]==0){
                visit[newnum]=1;
                q.push({newnum,cnt+1});
            }
        }
        //10
        for(int i=0 ; i<=9 ; i++){
            int nf=i*10;
            int newnum= f*1000 + s*100 + nf +fo;
           // cout<<"nuw"<<newnum<<endl;
            if(visit[newnum]==0){
                visit[newnum]=1;
                q.push({newnum,cnt+1});
            }
        }

        for(int i=0 ; i<=9 ; i++){
            int nf=i;
            int newnum= f*1000 + s*100 + t*10 +i;
         //   cout<<"nuw"<<newnum<<endl;
            if(visit[newnum]==0){
                visit[newnum]=1;
                q.push({newnum,cnt+1});
            }
        }
  //      cout<<f<<" "<<s<<" "<<t<<" "<<fo<<endl;
    }
}
void init(){
    memset(visit,0,sizeof(visit));
    for(int i=2; i <=9999; i++){
        int cnt=2;
        for(int j=cnt*i ; j<=9999; cnt++)
        { 
            if(visit[j]==0){
                visit[j]=1;
            }
            j=cnt*i;
        }
    }
}
int main(){
    int t;
    cin>>t;
    for(int tc=1;tc<=t;tc++){
        cin>>startv>>endv;
        ans=987654321;
        init();
        solve();
       // cout<<visit[8017]<<endl;
        if(ans==987654321){
            cout<<"Impossible"<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    
    }

    
    
}