CONY的世界

題目落落長 https://codejam.withgoogle.com/codejam/contest/dashboard?c=8384486#s=p2

簡化來說就是要判斷如果是任意 字母排序，判斷某word 是否可以在中間

Input

The first line of the input gives the number of test cases, T; T test cases follow. Each begins with one line containing one integer L: the length of each candidate's name. Then, there is one line with three different strings N_i of uppercase letters of the English alphabet; the i-th of these is the name of the i-th candidate.

Output

For each test case, output one line containing Case #x: y1 y2 y3, where x is the test case number (starting from 1) and each yi is YES if it is possible for the i-th candidate to be in the middle, as described in the problem statement, and NO otherwise.

Limits

1 ≤ T ≤ 100.
1 ≤ L ≤ 100.
N_i is of length L, for all i.
N_i ≠ N_j, for all i ≠ j.

Small dataset

N_i contains only uppercase letters from the set {A, B, C}, for all i.

Large dataset

N_i contains only uppercase letters from the English alphabet, for all i.

Sample

3
3
BCB CAB CBC
2
CC CA AA
6
MEDIAN MEDIAL MEDIAS

Case #1: NO YES YES
Case #2: NO YES NO
Case #3: YES YES YES

多虧學姊指點才搞懂這題，基本上想簡單一點就是每兩個字可以建立一個directed 關係（edge）

然後只要detect 這個directed graph 中有cycle 就表示不可能會有這種order

所以今天三個word 就是我們會得到兩個關係，

ex. BCB CAB 的關係就是 B->C ，CAB CBC 的關係就是 A->B

只要這兩個關係不要互斥我們就可以保證一定有一個 字母order 是可以使該word 在中間的

ex. A->B , B->C ==> A->B->C      or.    A->B, A->D ==> A->B->D or A->D->B

然後我們要想的就是什麼樣的情形會知道某word 不可能在中間，

其實就是互斥的時候 （A->B, B->A) 因為形成 cycle 了

而四個不同點 和 三個不同點都不會使關係互斥

所以接下來就是只要找兩個關係中只有兩個點且互斥的情形

（p.s 1. 用checkRelaion 來找是否能把a,b,c 分別放到中間，至於前後是誰不重要，因為這是swaptable的，因為可以任意字母order 

ex. A->B->C <==> C->B->A   ，B都是在中間，結果是一樣的

p.s 2. 因為break 在三個word 中第一個有不同的點，不表示三個點都會不同，也是有可能會有兩點相同的情形

所以要去判斷是否要去找第二個關係，如果要就 call checkRelation2 )

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Centrist {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
	    int testcase = in.nextInt(); 
	    for(int t=1; t <= testcase; t++) {
	    		int len = in.nextInt();
	    		String a=in.next(),b=in.next(),c=in.next();
	    		while(a.charAt(0) == b.charAt(0) && b.charAt(0) == c.charAt(0)) {
	    			a = a.substring(1,a.length());
	    			b = b.substring(1,b.length());
	    			c = c.substring(1,c.length());
	    		}
	    		System.out.println("Case #"+t+": "+checkRelation(b,a,c)+" "+checkRelation(a,b,c)+" "+checkRelation(a,c,b));
	    }
	}
	public static String checkRelation(String a, String b, String c) {
		if(a.charAt(0) == c.charAt(0))
			return "NO";
		if(a.charAt(0) == b.charAt(0)) 
			return checkRelation2(a,b, b.charAt(0), c.charAt(0));
		else if (b.charAt(0) == c.charAt(0))
			return checkRelation2(b,c,a.charAt(0), b.charAt(0));
		return "YES";
	}
	public static String checkRelation2(String a, String b, int x, int y) {
		while(a.charAt(0) == b.charAt(0)) {
			a = a.substring(1, a.length());
			b = b.substring(1, b.length());
		}
		return (a.charAt(0) == y && b.charAt(0) == x)?"NO":"YES";
	}
}