アルファベット移動-問題解

1.     

2 x 3=6個のマスにABCDE 5文字を入れ、右下のマスが空いています.図のように.
 
スペースに隣接するグリッドのアルファベットは、スペースに移動できます.たとえば、図のCとEは移動できます.移動後の状況は、次のようになります.
 
A B 
D E C
 
A B C
D   E
 
便宜上、6つの格子のアルファベット配置を1つの列で表します.例えば、上の2つの局面をそれぞれ表します.
 
 
 
AB*DEC
ABCD*E
 
問題の要求は:プログラムを編纂して、ユーザーがいくつかの局面を表す列を入力して、プログラムは計算を通じて、出力は初期状態に対して何度か移動してこの状態に着くことができるかどうかです.出力1を実現できます.そうしないと0を出力します.初期状態:ABCDE*
   
ユーザが入力するフォーマットは、まず整数nであり、次にn行の状態があることを示す.プログラム出力もn行1または0であるべきである
 
たとえば、ユーザー入力:
 
3
ABCDE*
AB*DEC
CAED*B
 
プログラムは次のように出力されます.
1
1
0
問題解決の考え方:
データ量が少ないので、直接検索します!より良い最適化は行われていませんが、十分なはずです.

import java.util.ArrayList;
import java.util.Scanner;


/**
 * 
 *   
 *       
 *
 */

public class Main
{
	public static int dir[] = {-3, 3, -1, 1};     //   ：  、 、 、 
	public static boolean flag = false;           //       
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s[] = new String[n];
		sc.nextLine();
		for (int i = 0; i < n; i++) s[i] = sc.nextLine();
		sc.close();
		
		for (int i = 0; i < n; i++)
		{
			flag = false;  
	     ArrayList list = new ArrayList();  //     
	     dfs(s[i], list);
	     if (flag == false) System.out.println(0);
	     else               System.out.println(1);
		}
	}

	private static void dfs(String str, ArrayList list)
	{
		if (flag)  return;                   //    retur
        if (list.contains(str)) return ;     //      
        if (str.equals("ABCDE*"))            //   
        {
        	flag = true;
        	return ;
    	}
        list.add(str); //       
        
        //     
        int index = str.indexOf("*");     
        //  
        if (index >= 3 && index <= 5)
        dfs(swap(str, index, 0), list);
        //  
        if (index >= 0 && index <= 2)
        dfs(swap(str, index, 1), list);
        //  
        if (index != 0 && index != 3)
        dfs(swap(str, index, 2), list);
        //  
        if (index != 2 && index != 5)
        dfs(swap(str, index, 3), list);
        
	}

	private static String swap(String str, int i, int j)
	{
		char crr[] = str.toCharArray();
		char ch = crr[i];
		crr[i] = crr[i+dir[j]];
		crr[i+dir[j]] = ch;
		return String.valueOf(crr);
	}
}