/home/toolbox/public_html/solutions/114/11405/a.cpp
1 #include <iostream>
2 #define MAX_INT 3207
3 #define INIT_VAL -1
4 #define BLOCKED_SQUARE -9
5 #define BOARD_SIZE 8
6 #define EMPTY '.'
7 #define PAWN 'P'
8 #define KNIGHT 'k'
9 #define MAX_PAWNS 10
10
11 using namespace std;
12
13 char board[BOARD_SIZE][BOARD_SIZE];
14 int distBoard[BOARD_SIZE][BOARD_SIZE];
15 int table[MAX_PAWNS][MAX_PAWNS];
16
17 int pawns[MAX_PAWNS][2];
18 int moveLimit;
19 int pawnCount;
20
21 void printBoard()
22 {
23 /* BEGIN FUNCTION printBoard */
24 std::cerr << "-----" << std::endl;
25 std::cerr << "Board pawnCount = " << pawnCount << std::endl;
26 std::cerr << "----" << std::endl;
27 for (int x = 0; BOARD_SIZE > x; x++)
28 {
29 /* for x */
30 for (int y = 0; BOARD_SIZE > y; y++)
31 {
32 /* for y */
33 std::cerr << " " << board[x][y];
34 } /* for y */
35 std::cerr << std::endl;
36 } /* for x */
37 std::cerr << std::endl;
38 std::cerr << std::endl;
39 } /* END FUNCTION printBoard */
40
41 void printTable()
42 {
43 /* BEGIN FUNCTION printTable */
44 std::cerr << "-----" << std::endl;
45 std::cerr << "Table pawnCount = " << pawnCount << std::endl;
46 std::cerr << "-----" << std::endl;
47 for (int x = 0; x < pawnCount; x++)
48 {
49 /* for x */
50 for (int y = 1; y < pawnCount; y++)
51 {
52 /* for y */
53 if (0 <= table[x][y])
54 std::cerr << " ";
55 std::cerr << " " << table[x][y];
56 } /* for y */
57 std::cerr << std::endl;
58 } /* for x */
59 std::cerr << std::endl;
60 std::cerr << std::endl;
61 } /* END FUNCTION printTable */
62
63
64 void printDistBoard()
65 {
66 /* BEGIN FUNCTION printDistBoard */
67 std::cerr << "---------" << std::endl;
68 std::cerr << "distTable" << std::endl;
69 std::cerr << "---------" << std::endl;
70 for (int x = 0; BOARD_SIZE > x; x++)
71 {
72 /* for x */
73 for (int y = 0; BOARD_SIZE > y; y++)
74 {
75 /* for y */
76 if (0 > distBoard[x][y])
77 std::cerr << " " << distBoard[x][y];
78 else
79 std::cerr << " " << distBoard[x][y];
80 } /* for y */
81 std::cerr << std::endl;
82 } /* for x */
83 std::cerr << std::endl;
84 std::cerr << std::endl;
85 } /* END FUNCTION printDistBoard */
86
87 bool checkSpace(int x, int y, int depth)
88 {
89 /* BEGIN FUNCTION checkSpace */
90 bool status = false;
91
92 if ((0 <= x) && (BOARD_SIZE > x) && (0 <= y) && (BOARD_SIZE > y))
93 {
94 /* x and y are okay */
95 if (INIT_VAL == distBoard[x][y])
96 {
97 /* found a valid square */
98 status = true;
99 distBoard[x][y] = depth + 1;
100 } /* found a valid square */
101 } /* x and y are okay */
102 /*
103 std::cerr << "checkspace depth = " << depth << " [" << x << "," << y << "] status = " << status << std::endl;
104 */
105 return status;
106 } /* END FUNCTION checkSpace */
107
108
109 bool markBoard(int depth)
110 {
111 /* BEGIN FUNCTION markBoard */
112 bool flag = false;
113 bool flag1,flag2,flag3,flag4,flag5,flag6,flag7,flag8;
114 for (int x = 0; BOARD_SIZE > x; x++)
115 {
116 /* for x */
117 for (int y = 0; BOARD_SIZE > y; y++)
118 {
119 /* for y */
120 if (distBoard[x][y] == depth)
121 {
122 /* right depth */
123 flag1 = checkSpace(x-2, y-1, depth);
124 flag2 = checkSpace(x-2, y+1, depth);
125 flag3 = checkSpace(x+2, y-1, depth);
126 flag4 = checkSpace(x+2, y+1, depth);
127 flag5 = checkSpace(x-1, y-2, depth);
128 flag6 = checkSpace(x-1, y+2, depth);
129 flag7 = checkSpace(x+1, y-2, depth);
130 flag8 = checkSpace(x+1, y+2, depth);
131 flag = flag || flag1 || flag2 || flag3 || flag4 || flag5 || flag6 || flag7 || flag8;
132 } /* right depth */
133 } /* for y */
134 } /* for x */
135 return flag;
136 } /* END FUNCTION markBoard */
137
138 void populateBoard(int i, int j)
139 {
140 /* BEGIN FUNCTION populateBoard */
141 for (int x = 0; BOARD_SIZE > x; x++)
142 {
143 /* for x */
144 for (int y = 0; BOARD_SIZE > y; y++)
145 {
146 /* for y */
147 if ((EMPTY == board[x][y]) || (PAWN == board[x][y]) ||(KNIGHT == board[x][y]))
148 distBoard[x][y] = INIT_VAL;
149 else
150 distBoard[x][y] = BLOCKED_SQUARE;
151 } /* for y */
152 } /* for x */
153 distBoard[i][j] = 0;
154 int x = 0;
155 std::cerr << "x=" << x << std::endl;
156 printDistBoard();
157 while (markBoard(x))
158 {
159 /* while */
160 x++;
161 std::cerr << "x=" << x << std::endl;
162 printDistBoard();
163 } /* while */
164 } /* END FUNCTION populateBoard */
165
166 void loadBoard()
167 {
168 /* BEGIN FUNCTION loadBoard */
169 std::cin >> moveLimit;
170 pawnCount = 1;
171 for (int x = 0; x < BOARD_SIZE; x++)
172 {
173 /* for x */
174 for (int y = 0; y < BOARD_SIZE; y++)
175 {
176 /* for y */
177 std::cin >> board[x][y];
178
179 if (KNIGHT == board[x][y])
180 {
181 /* knight found */
182 pawns[0][0] = x;
183 pawns[0][1] = y;
184 } /* knight found */
185
186 if (PAWN == board[x][y])
187 {
188 /* pawn found */
189 std::cerr << "Pawn: " << pawnCount << " [" << x << "," << y << "]" << std::endl;
190 pawns[pawnCount][0] = x;
191 pawns[pawnCount][1] = y;
192 pawnCount++;
193 } /* pawn found */
194 } /* for y */
195 } /* for x */
196 printBoard();
197 } /* END FUNCTION loadBoard */
198
199 int main()
200 {
201 int cases;
202 std::cin >> cases;
203 for (int i=0; i < cases; i++)
204 {
205 /* loop once for each case */
206 loadBoard();
207 for (int p = 0; p < pawnCount; p++)
208 {
209 /* for p */
210 populateBoard(pawns[p][0], pawns[p][1]);
211 for (int y = 1; y < pawnCount; y++)
212 {
213 /* for y */
214 if (p == y)
215 table[p][y] = 0;
216 else
217 table[p][y] = distBoard[pawns[y][0]][pawns[y][1]];
218 } /* for y */
219 } /* for p */
220 printTable();
221 /*for(int x = 0; x < pawnCount; x++) {
222 std::cerr << "Pawn " << x << ": " << pawns[x][0] << ", " << pawns[x][1] << std::endl;
223 }*/
224 } /* loop once for each case */
225 return 0;
226 }
227