The Java Program: A_block/blockYiu.java
1
2
3
4
5
6
7
8
9 import java.io.*;
10 import java.util.*;
11
12 public class blockYiu
13 {
14 public Scanner in = new Scanner(System.in);
15 public PrintStream out = System.out;
16
17 public int oo = 987654321;
18
19 public Map<String, Integer> cost;
20
21 public void main()
22 {
23 int i, j, k, x, y, z;
24 int C, len;
25 String now, code;
26 String special;
27 char[][] g;
28 boolean[] used;
29 char A;
30 int res;
31
32 special = in.next();
33 while(!"*".equals(special))
34 {
35
36 g = new char[6][];
37 for(i=0;i<6;++i) g[i] = in.next().toCharArray();
38
39
40 Queue<String> Q = new LinkedList<String>();
41
42 cost = new HashMap<String, Integer>();
43
44 res = oo;
45
46
47 code = cat(g);
48 cost.put(code, 0);
49 Q.offer(code);
50
51 BFS:
52 while(!Q.isEmpty())
53 {
54
55 now = Q.poll();
56 C = cost.get(now);
57
58
59 g = parse(now);
60 used = new boolean[26];
61
62
63 for(i=0;i<6;++i)
64 for(j=0;j<6;++j) if(g[i][j] != '.')
65 {
66 A = g[i][j];
67
68
69
70
71 if(used[A - 'A']) continue;
72 used[A - 'A'] = true;
73
74
75
76
77
78 if(special.charAt(0) == A && clear(g, i, j+2))
79 {
80 res = C+1;
81 break BFS;
82 }
83
84 if(j+1<6 && A == g[i][j+1])
85 {
86
87 len = (j+2 < 6 && A == g[i][j+2] ? 3 : 2);
88
89
90 for(k=j+1;k+len-1<6 && g[i][k+len-1]=='.';++k)
91 {
92
93
94 g[i][k-1] = '.';
95 g[i][k+len-1] = A;
96
97
98
99 code = cat(g);
100 if(!cost.containsKey(code))
101 {
102
103 cost.put(code, C+1);
104 Q.offer(code);
105 }
106 }
107
108
109 for(k=k+len-2;k>=0 && g[i][k]==A;--k) g[i][k] = '.';
110 for(z=0;z<len;++z) g[i][j+z] = A;
111
112
113 for(k=j-1;k>=0 && g[i][k]=='.';--k)
114 {
115
116 g[i][k+len] = '.';
117 g[i][k] = A;
118
119
120 code = cat(g);
121 if(!cost.containsKey(code))
122 {
123 cost.put(code, C+1);
124 Q.offer(code);
125 }
126 }
127
128
129
130 for(++k;k<6 && g[i][k]==A;++k) g[i][k] = '.';
131 for(z=0;z<len;++z) g[i][j+z] = A;
132 }
133 else
134 {
135
136 len = (i+2 < 6 && A == g[i+2][j] ? 3 : 2);
137
138 for(k=i+1;k+len-1<6 && g[k+len-1][j]=='.';++k)
139 {
140 g[k-1][j] = '.';
141 g[k+len-1][j] = A;
142
143 code = cat(g);
144 if(!cost.containsKey(code))
145 {
146 cost.put(code, C+1);
147 Q.offer(code);
148 }
149 }
150
151
152 for(k=k+len-2;k>=0 && g[k][j]==A;--k) g[k][j] = '.';
153 for(z=0;z<len;++z) g[i+z][j] = A;
154
155 for(k=i-1;k>=0 && g[k][j]=='.';--k)
156 {
157 g[k+len][j] = '.';
158 g[k][j] = A;
159
160 code = cat(g);
161 if(!cost.containsKey(code))
162 {
163 cost.put(code, C+1);
164 Q.offer(code);
165 }
166 }
167
168
169 for(++k;k<6 && g[k][j]==A;++k) g[k][j] = '.';
170 for(z=0;z<len;++z) g[i+z][j] = A;
171 }
172 }
173 }
174
175 out.println(res < oo ? res : -1);
176 special = in.next();
177 }
178 }
179
180
181
182 public boolean clear(char[][] g, int i, int j)
183 {
184 while(j < 6)
185 {
186 if(g[i][j] != '.') return false;
187 ++j;
188 }
189 return true;
190 }
191
192
193 public String cat(char[][] g)
194 {
195 StringBuffer ret = new StringBuffer("");
196 for(int i=0;i<g.length;++i) ret.append(new String(g[i]));
197 return ret.toString();
198 }
199
200
201 public char[][] parse(String s)
202 {
203 char[][] r = new char[6][];
204 for(int i=0;i<6;++i) r[i] = s.substring(i*6, (i+1)*6).toCharArray();
205 return r;
206 }
207
208 public static void main(String[] args)
209 {
210 long startTime = System.currentTimeMillis();
211 (new blockYiu()).main();
212 long endTime = System.currentTimeMillis();
213
214 System.err.println("Time = " + (endTime - startTime) + "(ms)");
215 }
216 }