로곡 P1242 신한노타 dfs 귀속

90분 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 50
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

//p1      ，p2      
int n,p1[MAX],p2[MAX],ans=0;

void dfs(int id,int pos1,int pos2){
    if(pos1==pos2){//       
        return;
    }
    for(int i=id-1;i>=1;i--){//    id          
        dfs(i,p1[i],6-pos1-pos2);
    }
    p1[id]=pos2;
    printf("move %d from %c to %c
",id,'A'+pos1-1,'A'+pos2-1);
    ans++;
}

int main(){
    scanf("%d",&n);
    int k,x;
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=1;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=2;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=3;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=1;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=2;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=3;}
    for(int i=n;i>=1;i--){
        dfs(i,p1[i],p2[i]);//  i                
    }
    printf("%d",ans);
    return 0;
}

시뮬레이션 퇴화도 가능(확률론?),근데 저는 잘 못해요.

AC 아이디어:

AC 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 50
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

struct node{
    int id;
    int s;
    int f;
}t_mov[1000005],mov[1000005];

//p1      ，p2      
int n,p1[MAX],p2[MAX],t1[MAX],t2[MAX],minl=INF,ans=0;

void dfs(int id,int pos1,int pos2){
    if(pos1==pos2){//       
        return;
    }
    for(int i=id-1;i>=1;i--){//    id          
        dfs(i,t1[i],6-pos1-pos2);
    }
    t1[id]=pos2;
    ans++;
    t_mov[ans].id=id,t_mov[ans].s=pos1,t_mov[ans].f=pos2;
}

int main(){
    scanf("%d",&n);
    int k,x;
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=1;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=2;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p1[x]=3;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=1;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=2;}
    scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&x);p2[x]=3;}

    for(int i=1;i<=2;i++){//    , 1      ， 2      
        ans=0;
        for(int j=1;j<=n;j++){//t1,t2    
            t1[j]=p1[j];
            t2[j]=p2[j];
        }
        if(i==1) dfs(n,t1[n],t2[n]);//    
        else dfs(n,t1[n],6-t1[n]-t2[n]);
        for(int j=n-1;j>=1;j--){
            dfs(j,t1[j],t2[j]);
        }
        for(int j=n;j>=1;j--){
            dfs(j,t1[j],t2[j]);
        }
        if(i==2){//      ，       n          
            for(int j=n;j>=1;j--){
                dfs(j,t1[j],t2[j]);
            }
        }
        if(ans<minl){
            for(int j=1;j<=ans;j++){
                mov[j]=t_mov[j];
            }
            minl=ans;
        }
    }
    for(int i=1;i<=minl;i++){
        printf("move %d from %c to %c
",mov[i].id,'A'+mov[i].s-1,'A'+mov[i].f-1);
    }
    printf("%d",minl);
    return 0;
}