C语言解答

#include<stdio.h>
#include<string.h>

int v[2000000],q[2000000];
int n;
int a[16];

int valid(int a[],int n) {
        int i;
        for(i=0;i+4<=n;i++)
                if (a[i]==2 && a[i+1]==0 && a[i+2]==1 && a[i+3]==2) return 1;
        return 0;
}

int trans1(int a[],int n) {
        int ret=0,i;
        for(i=0;i<n;i++) ret=ret*3+a[i];
        return ret;
}

void trans2(int a[],int n,int m) {
        int i;
        for(i=n-1;i>=0;i--) {
                a[i]=m%3;
                m/=3;
        }
}

int main() {
        char str[16];
        int i,j,t,m,tmp;
        memset(v,0xff,sizeof(v));
        while(scanf("%d",&n)!=EOF) {
                scanf("%s",str);
                for(i=0;i<n;i++) a[i]=str[i]-'0';
                m=trans1(a,n);
                v[m]=t=0,q[t++]=m;
                for(i=0;i<t;i++) {
                        trans2(a,n,q[i]);
                        if (valid(a,n)) break;
                        for(j=0;j<n-1;j++) {
                                tmp=a[j],a[j]=a[j+1],a[j+1]=tmp;
                                m=trans1(a,n);
                                if (v[m]<0) {
                                        v[m]=v[q[i]]+1;
                                        q[t++]=m;
                                }
                                tmp=a[j],a[j]=a[j+1],a[j+1]=tmp;
                        }
                }
                if (i<t) printf("%d\n",v[q[i]]); else puts("-1");
                for(i=0;i<t;i++) v[q[i]]=-1;
        }
        return 0;
}

C++解答

#include<stdio.h>
#include<string.h>

int v[2000000],q[2000000];
int n;
int a[16];

int valid(int a[],int n) {
	int i;
	for(i=0;i+4<=n;i++)
		if (a[i]==2 && a[i+1]==0 && a[i+2]==1 && a[i+3]==2) return 1;
	return 0;
}

int trans1(int a[],int n) {
	int ret=0,i;
	for(i=0;i<n;i++) ret=ret*3+a[i];
	return ret;
}

void trans2(int a[],int n,int m) {
	int i;
	for(i=n-1;i>=0;i--) {
		a[i]=m%3;
		m/=3;
	}
}

int main() {
	char str[16];
	int i,j,t,m,tmp;
	memset(v,0xff,sizeof(v));
	while(scanf("%d",&n)!=EOF) {
		scanf("%s",str);
		for(i=0;i<n;i++) a[i]=str[i]-'0';
		m=trans1(a,n);
		v[m]=t=0,q[t++]=m;
		for(i=0;i<t;i++) {
			trans2(a,n,q[i]);
			if (valid(a,n)) break;
			for(j=0;j<n-1;j++) {
				tmp=a[j],a[j]=a[j+1],a[j+1]=tmp;
				m=trans1(a,n);
				if (v[m]<0) {
					v[m]=v[q[i]]+1;
					q[t++]=m;
				}
				tmp=a[j],a[j]=a[j+1],a[j+1]=tmp;
			}
		}
		if (i<t) printf("%d\n",v[q[i]]); else puts("-1");
		for(i=0;i<t;i++) v[q[i]]=-1;
	}
	return 0;
}

Java解答

import java.util.*;

public class Main {
    static class Node {
        StringBuilder sb;
        int cnt;

        public Node() {
        }

        public Node(StringBuilder sb, int cnt) {
            this.sb = sb;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            sc.nextLine();
            System.out.println(bfs(sc.nextLine(), "2012"));
        }
    }

    private static int bfs(String s, String reg) {
        Queue<Node> queue = new LinkedList<>();
        HashSet<String> set = new HashSet<>();
        queue.add(new Node(new StringBuilder(s), 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            StringBuilder tem = node.sb;
            if (tem.toString().contains(reg)) return node.cnt;
            for (int i = 0; i < tem.length() - 1; i++) {
                StringBuilder next = new StringBuilder(tem.toString());
                swap(next, i, i + 1);
                if (set.contains(next.toString())) continue;
                else set.add(next.toString());
                if (next.toString().contains(reg)) return node.cnt + 1;
                queue.add(new Node(next, node.cnt + 1));
            }
        }
        return -1;
    }

    private static void swap(StringBuilder sb, int i, int j) {
        char temp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, temp);
    }

}