fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct Robot {
  7.     int x, y;
  8. };
  9.  
  10. // Function to precompute distances to nearest obstacles
  11. void precomputeDistances(vector<vector<char>>& matrix, vector<vector<int>>& left, vector<vector<int>>& top, vector<vector<int>>& right, vector<vector<int>>& bottom) {
  12.     int rows = matrix.size(), cols = matrix[0].size();
  13.  
  14.     // Initialize DP arrays with 0 (as robots themselves are valid starting points)
  15.     for (int i = 0; i < rows; i++) {
  16.         for (int j = 0; j < cols; j++) {
  17.             if (matrix[i][j] == 'X') {
  18.                 left[i][j] = top[i][j] = right[i][j] = bottom[i][j] = 0;
  19.             } else {
  20.                 left[i][j] = top[i][j] = right[i][j] = bottom[i][j] = -1;  // Mark uninitialized
  21.             }
  22.         }
  23.     }
  24.  
  25.     // Pass 1: Compute left and top distances
  26.     for (int i = 0; i < rows; i++) {
  27.         for (int j = 0; j < cols; j++) {
  28.             if (matrix[i][j] == 'X') continue;
  29.  
  30.             // Left Distance
  31.             if (j == 0 || matrix[i][j - 1] == 'X') 
  32.                 left[i][j] = 1; 
  33.             else 
  34.                 left[i][j] = left[i][j - 1] + 1;
  35.  
  36.             // Top Distance
  37.             if (i == 0 || matrix[i - 1][j] == 'X') 
  38.                 top[i][j] = 1; 
  39.             else 
  40.                 top[i][j] = top[i - 1][j] + 1;
  41.         }
  42.     }
  43.  
  44.     // Pass 2: Compute right and bottom distances
  45.     for (int i = rows - 1; i >= 0; i--) {
  46.         for (int j = cols - 1; j >= 0; j--) {
  47.             if (matrix[i][j] == 'X') continue;
  48.  
  49.             // Right Distance
  50.             if (j == cols - 1 || matrix[i][j + 1] == 'X') 
  51.                 right[i][j] = 1; 
  52.             else 
  53.                 right[i][j] = right[i][j + 1] + 1;
  54.  
  55.             // Bottom Distance
  56.             if (i == rows - 1 || matrix[i + 1][j] == 'X') 
  57.                 bottom[i][j] = 1; 
  58.             else 
  59.                 bottom[i][j] = bottom[i + 1][j] + 1;
  60.         }
  61.     }
  62. }
  63.  
  64. // Function to check if a robot satisfies the query
  65. bool isValidRobot(int i, int j, vector<int>& query, vector<vector<int>>& left, vector<vector<int>>& top, vector<vector<int>>& right, vector<vector<int>>& bottom) {
  66.     return left[i][j] == query[0] &&
  67.            top[i][j] == query[1] &&
  68.            right[i][j] == query[2] &&
  69.            bottom[i][j] == query[3];
  70. }
  71.  
  72. // Function to find robots matching the query
  73. vector<Robot> findRobots(vector<vector<char>>& matrix, vector<int>& query) {
  74.     int rows = matrix.size(), cols = matrix[0].size();
  75.  
  76.     // DP arrays to store distances
  77.     vector<vector<int>> left(rows, vector<int>(cols, -1));
  78.     vector<vector<int>> top(rows, vector<int>(cols, -1));
  79.     vector<vector<int>> right(rows, vector<int>(cols, -1));
  80.     vector<vector<int>> bottom(rows, vector<int>(cols, -1));
  81.  
  82.     // Precompute distances
  83.     precomputeDistances(matrix, left, top, right, bottom);
  84.  
  85.     vector<Robot> robots;
  86.     for (int i = 0; i < rows; i++) {
  87.         for (int j = 0; j < cols; j++) {
  88.             if (matrix[i][j] == 'O' && isValidRobot(i, j, query, left, top, right, bottom)) {
  89.                 robots.push_back({i, j});
  90.             }
  91.         }
  92.     }
  93.     return robots;
  94. }
  95.  
  96. int main() {
  97.     vector<vector<char>> matrix = {
  98.         {'O', 'E', 'E', 'E', 'E'},
  99.         {'E', 'O', 'X', 'E', 'E'},
  100.         {'X', 'E', 'X', 'X', 'E'},
  101.         {'E', 'E', 'O', 'X', 'E'},
  102.         {'X', 'E', 'X', 'E', 'E'}
  103.     };
  104.  
  105.     vector<int> query = {2, 2, 4, 1};
  106.     vector<Robot> robots = findRobots(matrix, query);
  107.  
  108.     cout << "Robots that match the query:\n";
  109.     for (auto& r : robots) {
  110.         cout << "Robot found at: (" << r.x << ", " << r.y << ")\n";
  111.     }
  112.  
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Robots that match the query:
https://ideone.com/PxIaZp
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!