/home/toolbox/public_html/solutions/114/11405/11405-working-submit.cpp
1 #include <iostream>
2
3 int asciitoint(char a)
4 {
5 return a-'A';
6 }
7
8 char inttoascii(int i)
9 {
10 return i+'A';
11 }
12
13 const int MAX = 10000;
14
15 using namespace std;
16
17 char board[8][8];
18 int dist[9][8][8];
19 int pawns[9][2];
20
21 int moveLimit;
22 int pawnCount;
23 int minimum=MAX;
24
25 void printBoard()
26 {
27 for(int x = 0; x < 8; x++)
28 {
29 for(int y = 0; y < 8; y++)
30 {
31 std::cerr << board[x][y];
32 }
33 std::cerr << std::endl;
34 }
35 std::cerr << std::endl;
36 }
37
38 void printDistances()
39 {
40 for(int v = 0; v < pawnCount; v++)
41 {
42 for(int i = 0; i < 8; i++)
43 {
44 for(int j = 0; j < 8; j++)
45 {
46 std::cerr << " " << dist[v][i][j] << " ";
47 }
48 std::cerr << std::endl;
49 }
50 std::cerr << std::endl;
51 }
52 std::cerr << std::endl;
53 std::cerr << std::endl;
54
55 }
56
57 void calcDistances(int vertex, int rank, int file)
58 {
59 for(int i = 0; i < 8; i++)
60 {
61 for(int j = 0; j < 8; j++)
62 {
63 if(board[i][j] == 'p' || board[i][j] == 'K')
64 {
65 dist[vertex][i][j] = -1;
66 }
67 else
68 {
69 dist[vertex][i][j] = MAX;
70 }
71 }
72 }
73 dist[vertex][rank][file] = 0;
74 bool flag = true;
75 int count = 0;
76 while(flag)
77 {
78 flag = false;
79 for(int i = 0; i < 8; i++)
80 {
81 for(int j = 0; j < 8; j++)
82 {
83 if(dist[vertex][i][j] == count)
84 {
85 ///////////////////////
86 if(i - 2 >= 0 && j + 1 < 8)
87 {
88 if(dist[vertex][i-2][j+1] > count + 1)
89 {
90 dist[vertex][i-2][j+1] = count + 1;
91 flag = true;
92 }
93 }
94 if(i - 2 >= 0 && j - 1 >= 0)
95 {
96 if(dist[vertex][i-2][j-1] > count + 1)
97 {
98 dist[vertex][i-2][j-1] = count + 1;
99 flag = true;
100 }
101 }
102 if(i + 2 < 8 && j - 1 >= 0)
103 {
104 if(dist[vertex][i+2][j-1] > count + 1)
105 {
106 dist[vertex][i+2][j-1] = count + 1;
107 flag = true;
108 }
109 }
110 if(i + 2 < 8 && j + 1 < 8)
111 {
112 if(dist[vertex][i+2][j+1] > count + 1)
113 {
114 dist[vertex][i+2][j+1] = count + 1;
115 flag = true;
116 }
117 }
118 ///////////////////
119 if(i - 1 >= 0 && j + 2 < 8)
120 {
121 if(dist[vertex][i-1][j+2] > count + 1)
122 {
123 dist[vertex][i-1][j+2] = count + 1;
124 flag = true;
125 }
126 }
127 if(i - 1 >= 0 && j - 2 >= 0)
128 {
129 if(dist[vertex][i-1][j-2] > count + 1)
130 {
131 dist[vertex][i-1][j-2] = count + 1;
132 flag = true;
133 }
134 }
135 if(i + 1 < 8 && j - 2 >= 0)
136 {
137 if(dist[vertex][i+1][j-2] > count + 1)
138 {
139 dist[vertex][i+1][j-2] = count + 1;
140 flag = true;
141 }
142 }
143 if(i + 1 < 8 && j + 2 < 8)
144 {
145 if(dist[vertex][i+1][j+2] > count + 1)
146 {
147 dist[vertex][i+1][j+2] = count + 1;
148 flag = true;
149 }
150 }
151 ////////////////////////
152 // printDistances();
153 // sleep(2);
154 }
155 }
156 }
157 count++;
158 }
159 }
160
161 int stringToDistance(std::string sequence)
162 {
163 int totalDist = 0;
164 for(unsigned int i = 0; i < sequence.length(); i++)
165 {
166 if(i + 1 != sequence.length())
167 {
168 int c = asciitoint(sequence[i]);
169 totalDist += dist[c][pawns[asciitoint(sequence[i+1])][0]][pawns[asciitoint(sequence[i+1])][1]];
170 }
171 }
172 return totalDist;
173 }
174
175 void sum(int left, std::string sequence)
176 {
177 if(left == 0)
178 {
179 int thisDistance = stringToDistance(sequence);
180 if(minimum > thisDistance)
181 {
182 minimum = thisDistance;
183 }
184 }
185 else
186 {
187 for(int i = 0; i < pawnCount; i++)
188 {
189 bool inSequence = false;
190 for(unsigned int j = 0; j < sequence.length(); j++)
191 {
192 if(sequence[j] == inttoascii(i))
193 {
194 inSequence = true;
195 }
196 }
197 if(inSequence == false)
198 {
199 sum(left-1, std::string(sequence+inttoascii(i)));
200 }
201 }
202 }
203 }
204
205 int main()
206 {
207 int cases;
208 std::cin >> cases;
209 while(cases > 0)
210 {
211 std::cin >> moveLimit;
212 minimum = MAX;
213 pawnCount = 1;
214 for(int i = 0; i < 8; i++)
215 {
216 for(int j = 0; j < 8; j++)
217 {
218 std::cin >> board[i][j];
219 if(board[i][j] == 'k')
220 {
221 pawns[0][0] = i;
222 pawns[0][1] = j;
223 }
224 else if(board[i][j] == 'P')
225 {
226 pawns[pawnCount][0] = i;
227 pawns[pawnCount][1] = j;
228 pawnCount++;
229 }
230 }
231 }
232 //printBoard();
233 for(int i = 0; i < 8; i++)
234 {
235 for(int j = 0; j < 8; j++)
236 {
237 if(board[i][j] == 'k')
238 {
239 calcDistances(0, i, j);
240 }
241 }
242 }
243 int currentPiece = 1;
244 for(int i = 0; i < 8; i++)
245 {
246 for(int j = 0; j < 8; j++)
247 {
248 if(board[i][j] == 'P')
249 {
250 calcDistances(currentPiece, i, j);
251 currentPiece++;
252 }
253 }
254 }
255 //printDistances();
256 sum(pawnCount-1, std::string("A"));
257 if(minimum <= moveLimit)
258 {
259 std::cout << "Yes" << std::endl;
260 }
261 else
262 {
263 std::cout << "No" << std::endl;
264 }
265 --cases;
266 }
267 return 0;
268 }
269