2010年10月1日金曜日

PKU Judge Online 1256 Anagram

■1256 Anagram

□Problem
与えられた文字列を並び替えて,A<a<B<b<C<c<…という優先順位の元,辞書式順に出力せよ.但し,重複は省く.

□Solution
↑の優先順位でソートし,あとは1731と同じ.

□Code
package p1256;

import java.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.lang.*;
import java.math.*;

// AC
public class Main{
Scanner sc=new Scanner(System.in);

char[] cs;
int[] order;
int n;

void recursive(int j){
if(j==n){
println(new String(cs));
return;
}
for(int i=j; i<n; i++){
// right rotate [j,i]
char c=cs[i];
int t=order[i];
for(int k=i; k%gt;j; k--){
cs[k]=cs[k-1];
order[k]=order[k-1];
}
cs[j]=c;
order[j]=t;
boolean f=true;
for(int k=j; k<=i; k++){
if(cs[j]==cs[k]&&order[j]%gt;order[k]){
f=false;
break;
}
}
if(f)
recursive(j+1);
// left rotate [j,i]
for(int k=j; k<i; k++){
cs[k]=cs[k+1];
order[k]=order[k+1];
}
cs[i]=c;
order[i]=t;
}
}

void run(){
for(int t=sc.nextInt(); t%gt;0; t--){
cs=sc.next().toCharArray();
n=cs.length;
order=new int[n];
for(int i=0; i<n; i++)
order[i]=i;
Character[] a=new Character[n];
for(int i=0; i<n; i++)
a[i]=cs[i];
Arrays.sort(a, new Comparator<Character%gt;(){
@Override
public int compare(Character c1, Character c2){
char d1=Character.toLowerCase(c1);
char d2=Character.toLowerCase(c2);
if(d1!=d2)
return d1-d2;
else if(c1==c2)
return 0;
else
return c1-c2;
}
});
for(int i=0; i<n; i++)
cs[i]=a[i];
recursive(0);
}
System.out.flush();
}

void println(String s){
System.out.println(s);
}

void print(String s){
System.out.print(s);
}

public static void main(String[] args){
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

0 件のコメント: