#include <stdio.h> int grid_width, grid_height; char grid_sym[2510]; int grid_dist_kennel[2500]; int grid_dist_thief[2500]; int grid_dist_exit[2500]; int exits[200]; #define FFQC 2510 int ffq_pop_idx = 0, ffq_push_idx = 0; int ffqp[FFQC], ffqd[FFQC]; void ffq_push(int pos, int depth) { ffqp[ffq_push_idx] = pos; ffqd[ffq_push_idx] = depth; ffq_push_idx = (ffq_push_idx + 1) % FFQC; } int ffq_pop(int *pos, int *depth) { if (ffq_pop_idx == ffq_push_idx) return 0; *pos = ffqp[ffq_pop_idx]; *depth = ffqd[ffq_pop_idx]; ffq_pop_idx = (ffq_pop_idx + 1) % FFQC; return 1; } void flood_fill(int start_pos, int *distances, int(*should_visit)(int, int)) { for (int i = 0; i < 2500; ++i) { distances[i] = -1; } ffq_push(start_pos, 0); int pos, depth; while (ffq_pop(&pos, &depth)) { if (distances[pos] == -1 && grid_sym[pos] != 'X' && should_visit(pos, depth)) { distances[pos] = depth; const int row = pos / grid_width; const int col = pos % grid_width; if (row > 0) ffq_push(pos - grid_width, depth + 1); if (col > 0) ffq_push(pos - 1, depth + 1); if (col + 1 < grid_width) ffq_push(pos + 1, depth + 1); if (row + 1 < grid_height) ffq_push(pos + grid_width, depth + 1); } } } int should_visit_thief(int pos, int depth) { const int thief_exit_time = depth + grid_dist_exit[pos]; const int dog_exit_time = grid_dist_kennel[pos] + (grid_dist_exit[pos] + 1) / 2; return thief_exit_time < dog_exit_time; } int should_visit_other(int pos, int depth) { return 1; } void handle_case() { int thief, kennel, num_exits = 0; for (int i = grid_width * grid_height; i > 0; --i) { switch (grid_sym[i]) { case 'T': thief = i; break; case 'K': kennel = i; break; case 'E': exits[num_exits++] = i; } } flood_fill(kennel, grid_dist_kennel, should_visit_other); for (int i = 0; i < num_exits; ++i) { flood_fill(exits[i], grid_dist_exit, should_visit_other); flood_fill(thief, grid_dist_thief, should_visit_thief); if (grid_dist_thief[exits[i]] >= 0) { puts("KEEP IT"); return; } } puts("DROP IT"); } int main() { while (scanf("%d %d ", &grid_width, &grid_height) == 2 && grid_width >= 3 && grid_height >= 3) { for (int row = 0; row < grid_height; ++row) { fgets(&grid_sym[row * grid_width], 60, stdin); } handle_case(); } }