/home/toolbox/public_html/solutions/114/11405/11405-2.cpp
1 #include <iostream>
2 #define MAX_INT 3207
3 #define INIT_VAL -9
4
5 using namespace std;
6
7 char board[8][8];
8 int distBoard[8][8];
9 int table[9][9];
10
11 int pawns[8][2];
12 int moveLimit;
13 int pawnCount;
14
15 void printBoard()
16 {
17 for(int x = 0; x < 8; x++)
18 {
19 for(int y = 0; y < 8; y++)
20 {
21 std::cerr << board[x][y];
22 }
23 std::cerr << std::endl;
24 }
25 std::cerr << std::endl;
26 }
27
28 void printTable()
29 {
30 std::cerr << "table: " << std::endl;
31 for(int x = 0; x < pawnCount; x++)
32 {
33 for(int y = 0; y < pawnCount; y++)
34 {
35 std::cerr << table[x][y];
36 }
37 std::cerr << std::endl;
38 }
39 std::cerr << std::endl;
40 }
41
42 void printDistBoard()
43 {
44 for(int x = 0; x < 8; x++)
45 {
46 for(int y = 0; y < 8; y++)
47 {
48 if(distBoard[x][y] < 0)
49 std::cerr << " " << distBoard[x][y];
50 else
51 std::cerr << " " << distBoard[x][y];
52 }
53 std::cerr << std::endl;
54 }
55 std::cerr << std::endl;
56 }
57
58 bool markBoard(int depth)
59 {
60 bool flag = false;
61 for(int x=0; x<8; x++)
62 {
63 for(int y=0; y<8; y++)
64 {
65 if(distBoard[x][y] == depth)
66 {
67 if(x-2 >= 0 && y-1 >= 0 && distBoard[x-2][y-1] == INIT_VAL)
68 {
69 distBoard[x-2][y-1] = depth+1;
70 flag = true;
71 }
72 if(x-2 >= 0 && y+1 < 8 && distBoard[x-2][y+1] == INIT_VAL)
73 {
74 distBoard[x-2][y+1] = depth+1;
75 flag = true;
76 }
77 if(x+2 < 8 && y-1 >= 0 && distBoard[x+2][y-1] == INIT_VAL)
78 {
79 distBoard[x+2][y-1] = depth+1;
80 flag = true;
81 }
82 if(x+2 < 8 && y+1 < 8 && distBoard[x+2][y+1] == INIT_VAL)
83 {
84 distBoard[x+2][y+1] = depth+1;
85 flag = true;
86 }
87 if(x-2 >= 0 && y-2 >= 0 && distBoard[x-2][y-2] == INIT_VAL)
88 {
89 distBoard[x-2][y-2] = depth+1;
90 flag = true;
91 }
92 if(x-1 >= 0 && y+2 < 8 && distBoard[x-1][y+2] == INIT_VAL)
93 {
94 distBoard[x-1][y+2] = depth+1;
95 flag = true;
96 }
97 if(x+1 < 8 && y-2 >= 0 && distBoard[x+1][y-2] == INIT_VAL)
98 {
99 distBoard[x+1][y-2] = depth+1;
100 flag = true;
101 }
102 if(x+1 < 8 && y+2 < 8 && distBoard[x+1][y+2] == INIT_VAL)
103 {
104 distBoard[x+1][y+2] = depth+1;
105 flag = true;
106 }
107 }
108 }
109 }
110 return flag;
111 }
112
113 void populateBoard(int i, int j)
114 {
115 for(int x=0; x<8; x++)
116 {
117 for(int y=0; y<8; y++)
118 {
119 distBoard[x][y] = INIT_VAL;
120 }
121 }
122 distBoard[i][j] = 0;
123 int x = 0;
124 while(markBoard(x))
125 {
126 x++;
127 }
128 printDistBoard();
129 }
130
131 int main()
132 {
133 int cases;
134 std::cin >> cases;
135 while(cases > 0)
136 {
137 std::cin >> moveLimit;
138 pawnCount = 1;
139 for(int x = 0; x < 8; x++)
140 {
141 for(int y = 0; y < 8; y++)
142 {
143 std::cin >> board[x][y];
144 if(board[x][y] == 'k')
145 {
146 pawns[0][0] = x;
147 pawns[0][1] = y;
148 }
149 if(board[x][y] == 'P')
150 {
151 pawns[pawnCount][0] = x;
152 pawns[pawnCount][1] = y;
153 pawnCount++;
154 }
155 std::cerr << board[x][y];
156 }
157 std::cerr << std::endl;
158 }
159 for(int x = 0; x < pawnCount; x++)
160 {
161 populateBoard(pawns[x][0], pawns[x][1]);
162 for(int y = 0; y < pawnCount; y++)
163 {
164 if(x == y) table[x][y] = 0;
165 else
166 {
167 table[x][y] = distBoard[pawns[y][0]][pawns[y][1]];
168 }
169 }
170 }
171 printTable();
172 /*for(int x = 0; x < pawnCount; x++) {
173 std::cerr << "Pawn " << x << ": " << pawns[x][0] << ", " << pawns[x][1] << std::endl;
174 }*/
175 --cases;
176 }
177 return 0;
178 }
179