阿祁的部落格

CSES 2427 - Letter Pair Move Game  解題心得( 題目 )

解題概念:觀察規律

解題方法:這題不像是演算法題目，雖然看起來很圖論，但我們可透過觀察規律，可以發現一致的解題流程，且最終次數不超過題目限制。

Java參考程式碼(有更好意見可留言於下方，謝謝!)

import java.io.*;

import java.util.*;

import java.math.*;

public class cses2427 {

    public static int ret,r;

    public static int n,n2,cnt,idx;

    public static char[][] ans=new char[1005][205];

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static void main(String[] args) throws Exception{

        n=Integer.parseInt(br.readLine())-1;

        n2=(n+1)<<1;

        String in=br.readLine();

        for(int i=0;i<n2;i++) {

            ans[0][i]=in.charAt(i);

        }


        if(n==1) { //only one pair

            boolean noAns=true;

            for(int i=0;i<n2;i++) {

                if(ans[0][i]=='A')noAns=false;

                if(ans[0][i]=='B')break;

            }


            bw.write(noAns?"-1":"0");

        }

        else {

            run();

        }

        bw.flush();

      }

    


    public static void run() throws Exception{

        idx=findEmpty();

        while(idx<n2-3) {

            move(idx+2,idx);

            idx+=2;

        }

        if(idx%2!=0)roll();

        int Acnt=0;

        steps:

        for(int i=0;Acnt<n&&i<n2;i++) {

            if(ans[cnt][i]=='B') {

                for(int j=i+2;j<n2-3;j++) {

                    if(ans[cnt][j]=='A') {

                        swap(i,j);

                        Acnt++;

                        continue steps;

                    }

                }

                move(i,n2-2);

                if(ans[cnt][n2-3]=='A'&&n>2) {

                    move(n2-3,i);

                }

                break steps;

            }

        }

        boolean noAns=false;

        Acnt=0;

        for(int i=0;Acnt<n;i++) {

            if(ans[cnt][i]=='A') {

                Acnt++;

            }

            if(ans[cnt][i]=='B') {

                noAns=true;

                break;

            }

        }

        if(noAns) {

            bw.write("-1");

        }

        else {

            bw.write(cnt+"\n");

            for(int i=1;i<=cnt;i++) {

                for(int j=0;j<n2;j++) {

                    bw.write(ans[i][j]);

                }

                bw.write("\n");

            }

        }

        return;

    }

    

    public static void roll() {

        move(n2-6,n2-3);

        move(n2-4,n2-6);

        move(n2-2,n2-4);

    }

    


    public static void swap(int a,int b) {

        move(a,n2-2);

        move(b,a);

        move(n2-2,b);

    }

    

    public static void move(int ip,int ie){

        cnt++;

        for(int i=0;i<n2;i++) {

            ans[cnt][i]=ans[cnt-1][i];

        }

        ans[cnt][ie]=ans[cnt-1][ip];

        ans[cnt][ie+1]=ans[cnt-1][ip+1];

        ans[cnt][ip]='.';

        ans[cnt][ip+1]='.';

    }


    

    public static int findEmpty() {

        for(int i=0;i<n2;i++) {

            if(ans[0][i]=='.')return i;

        }

        return 0;//never reach here

    }

}