#include <array> #include <cassert> #include <deque> #include <iostream> #include <string> #include <tuple> #include <vector> using namespace std; const int max_grid_width = 50; const int max_grid_height = 50; const int max_grid_cells = max_grid_width * max_grid_height; int grid_width, grid_height; array<char, max_grid_cells> grid_sym; array<int, max_grid_cells> grid_dist_kennel; array<int, max_grid_cells> grid_dist_thief; array<int, max_grid_cells> grid_dist_exit; void flood_fill( int start_pos, array<int, max_grid_cells>& distances, bool(*should_visit)(int, int)=[](int, int) { return true; }) { distances.fill(-1); deque<tuple<int, int>> to_visit; to_visit.emplace_back(start_pos, 0); while (!to_visit.empty()) { int pos, depth; tie(pos, depth) = to_visit.front(); to_visit.pop_front(); 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) to_visit.emplace_back(pos - grid_width, depth + 1); if (col > 0) to_visit.emplace_back(pos - 1, depth + 1); if (col + 1 < grid_width) to_visit.emplace_back(pos + 1, depth + 1); if (row + 1 < grid_height) to_visit.emplace_back(pos + grid_width, depth + 1); } } } void handle_case() { int thief, kennel; vector<int> exits; int grid_size = grid_width * grid_height; for (int i = 0; i < grid_size; ++i) { switch (grid_sym[i]) { case 'T': thief = i; break; case 'K': kennel = i; break; case 'E': exits.push_back(i); } } flood_fill(kennel, grid_dist_kennel); for (int exit : exits) { flood_fill(exit, grid_dist_exit); flood_fill(thief, grid_dist_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; }); if (grid_dist_thief[exit] >= 0) { cout << "KEEP IT\n"; return; } } cout << "DROP IT\n"; } int main() { string line; while (cin >> grid_width >> grid_height && grid_width >= 3 && grid_height >= 3) { getline(cin, line); assert(grid_width <= max_grid_width); assert(grid_height <= max_grid_height); for (int row = 0; row < grid_height; ++row) { getline(cin, line); assert(line.size() >= static_cast<size_t>(grid_width)); for (int col = 0; col < grid_width; ++col) { grid_sym[row * grid_width + col] = line[col]; } } handle_case(); } }