## Intuition The problem involves determining if a given grid of letters can be constructed by drawing straight snakes (either horizontal or vertical) over an initially empty grid. Each snake corresponds to a unique letter, and the order of drawing matters as snakes can overwrite previous ones. The key insight is to identify the boundaries of each letter's presence in the grid and verify if they can be represented as a straight line. ## Approach 1. **Identify Boundaries:** For each letter present in the grid, determine the minimum and maximum row and column indices where the letter appears. This gives us the potential boundaries of the snake. 2. **Validate Snake Formation:** For each letter, check if the identified boundaries form a valid straight line (either horizontal or vertical). If a letter appears in a non-linear fashion, it's impossible to form a snake. 3. **Check Overwriting Order:** Since snakes can overwrite previous ones, we need to ensure that the drawing order respects the constraints. This means processing letters in reverse order of their appearance (from 'z' to 'a'). 4. **Output Results:** If all letters can be represented as valid snakes, print "YES" and the coordinates of each snake. Otherwise, print "NO". ## Complexity - **Time:** O(n * m) per test case, where n and m are the dimensions of the grid. This is because we traverse the grid multiple times for boundary detection and validation. - **Space:** O(1) additional space, apart from input storage. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector grid(n); for (int i = 0; i < n; ++i) { cin >> grid[i]; } vector> snakes(26, {-1, -1, -1, -1}); vector exists(26, false); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] != '.') { int idx = grid[i][j] - 'a'; exists[idx] = true; if (get<0>(snakes[idx]) == -1) { snakes[idx] = {i, j, i, j}; } else { get<0>(snakes[idx]) = min(get<0>(snakes[idx]), i); get<1>(snakes[idx]) = min(get<1>(snakes[idx]), j); get<2>(snakes[idx]) = max(get<2>(snakes[idx]), i); get<3>(snakes[idx]) = max(get<3>(snakes[idx]), j); } } } } bool possible = true; vector> result; for (int i = 25; i >= 0; --i) { if (exists[i]) { int r1 = get<0>(snakes[i]), c1 = get<1>(snakes[i]); int r2 = get<2>(snakes[i]), c2 = get<3>(snakes[i]); if (r1 != r2 && c1 != c2) { possible = false; break; } char ch = 'a' + i; for (int r = r1; r <= r2; ++r) { for (int c = c1; c <= c2; ++c) { if (grid[r][c] != ch) { possible = false; break; } } if (!possible) break; } if (!possible) break; result.push_back({r1 + 1, c1 + 1, r2 + 1, c2 + 1}); } } if (possible) { cout << "YES\n" << result.size() << "\n"; for (auto &snake : result) { cout << get<0>(snake) << " " << get<1>(snake) << " " << get<2>(snake) << " " << get<3>(snake) << "\n"; } } else { cout << "NO\n"; } } return 0; } ``` This solution efficiently checks the possibility of forming the grid using snakes and outputs the required coordinates if possible.

Polycarp and Snakes

Problem Details