/home/toolbox/public_html/solutions/114/11405/11405.cpp
1 #include <iostream>
2
3 #define MAX_INT 3207
4 char board[8][8];
5 int table[9][9];
6
7 int pawns[8][2];
8 int moveLimit;
9
10 void printBoard()
11 {
12 for(int x = 0; x < 8; x++)
13 {
14 for(int y = 0; y < 8; y++)
15 {
16 std::cerr << board[x][y];
17 }
18 std::cerr << std::endl;
19 }
20 std::cerr << std::endl;
21 }
22 /* returns minimum number of length for knight to get between points*/
23 int knightCapability(int x1, int y1, int x2, int y2, int totalLength)
24 {
25 if(totalLength > moveLimit+9)
26 {
27 //std::cerr << "move limit exceeded" << std::endl;
28 return MAX_INT-3;
29 }
30 if(x1 < 0 || y1 < 0 || x1 > 7 || y1 > 7)
31 {
32 //std::cerr << "out of bounds" << std::endl;
33 return MAX_INT-2;
34 }
35 if(board[x1][y1] != '.' && board[x1][y1] != 'k' && board[x1][y1] != 'P')
36 {
37 //std::cerr << "not . or P" << std::endl;
38 return MAX_INT-4;
39 }
40 if(x1 == x2 && y1 == y2)
41 {
42 return totalLength;
43 }
44 //std::cerr << "(" << x1 << ", " << y1 << ")" << std::endl;
45 //printBoard();
46 int minimum = 77777;
47 int moveLength[8];
48 char temp = board[x1][y1];
49 board[x1][y1] = '`';
50 //std::cerr << "---------------" << std::endl;
51 moveLength[0] = knightCapability(x1-2, y1-1, x2, y2, totalLength+1);
52 moveLength[1] = knightCapability(x1-2, y1+1, x2, y2, totalLength+1);
53 moveLength[2] = knightCapability(x1+2, y1-1, x2, y2, totalLength+1);
54 moveLength[3] = knightCapability(x1+2, y1+1, x2, y2, totalLength+1);
55 moveLength[4] = knightCapability(x1-1, y1-2, x2, y2, totalLength+1);
56 moveLength[5] = knightCapability(x1-1, y1+2, x2, y2, totalLength+1);
57 moveLength[6] = knightCapability(x1+1, y1-2, x2, y2, totalLength+1);
58 moveLength[7] = knightCapability(x1+1, y1+2, x2, y2, totalLength+1);
59 //std::cerr << "+++++++++++++++" << std::endl;
60 board[x1][y1] = temp;
61 for(int x = 0; x < 8; x++)
62 {
63 if(moveLength[x] < minimum)
64 {
65 minimum = moveLength[x];
66 }
67 }
68 //std::cerr << "found min: " << minimum << std::endl;
69 return minimum;
70 }
71
72 int main()
73 {
74 int cases;
75 std::cin >> cases;
76 while(cases > 0)
77 {
78 int pawnCount = 1;
79 std::cin >> moveLimit;
80 for(int x = 0; x < 8; x++)
81 {
82 for(int y = 0; y < 8; y++)
83 {
84 std::cin >> board[x][y];
85 if(board[x][y] == 'k')
86 {
87 pawns[0][0] = x;
88 pawns[0][1] = y;
89 }
90 if(board[x][y] == 'P')
91 {
92 pawns[pawnCount][0] = x;
93 pawns[pawnCount][1] = y;
94 pawnCount++;
95 }
96 std::cerr << board[x][y];
97 }
98 std::cerr << std::endl;
99 }
100 for(int x = 0; x < pawnCount; x++)
101 {
102 std::cerr << "Pawn " << x << ": " << pawns[x][0] << ", " << pawns[x][1] << std::endl;
103 }
104 for(int x = 0; x < pawnCount; x++)
105 {
106 for(int y = 0; y < pawnCount; y++)
107 {
108 //distance from pawn/knight x to pawn/knight y
109 if(x == y) table[x][y] = 0;
110 else
111 {
112 table[x][y] = knightCapability(pawns[x][0],
113 pawns[x][1],
114 pawns[y][0],
115 pawns[y][1], 0);
116 }
117 std::cerr << "Calculated distance from pawns[" << x << "]: " << pawns[x][0] << ", " << pawns[x][1] << " to pawns[" << y << "]: " << pawns[y][0] << ", " << pawns[y][1] << " = " << '\'' << table[x][y] << '\'' << std::endl;
118 }
119 }
120 --cases;
121 }
122 return 0;
123 }
124