fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <queue>
  5. #include <utility> // For std::pair
  6.  
  7. using namespace std;
  8.  
  9. // Directions for 4-way movement (Up, Down, Left, Right)
  10. const int DR[] = {-1, 1, 0, 0};
  11. const int DC[] = {0, 0, -1, 1};
  12.  
  13. void solve() {
  14.     // Optimization for faster I/O
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17.  
  18.     int N, M, K;
  19.     if (!(cin >> N >> M >> K)) return;
  20.  
  21.     vector<string> grid(N);
  22.     int total_dots = 0;
  23.     int start_r = -1, start_c = -1;
  24.  
  25.     // 1. Read input and find statistics
  26.     for (int i = 0; i < N; ++i) {
  27.         cin >> grid[i];
  28.         for (int j = 0; j < M; ++j) {
  29.             if (grid[i][j] == '.') {
  30.                 total_dots++;
  31.                 if (start_r == -1) {
  32.                     start_r = i; // Store the coordinates of the first dot found
  33.                     start_c = j;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.  
  39.     // Determine the target number of dots to keep connected
  40.     // We must turn K dots into 'X', so we keep D - K dots.
  41.     int target_keep = total_dots - K;
  42.  
  43.     // Handle case where we need to keep 0 or fewer dots
  44.     if (target_keep <= 0) {
  45.         for (int i = 0; i < N; ++i) {
  46.             for (int j = 0; j < M; ++j) {
  47.                 if (grid[i][j] == '.') {
  48.                     grid[i][j] = 'X';
  49.                 }
  50.             }
  51.         }
  52.         for (int i = 0; i < N; ++i) {
  53.             cout << grid[i] << "\n";
  54.         }
  55.         return;
  56.     }
  57.  
  58.     // 2. BFS implementation to find the target_keep connected dots
  59.  
  60.     vector<vector<bool>> visited(N, vector<bool>(M, false));
  61.     queue<pair<int, int>> q;
  62.     int dots_kept = 0;
  63.  
  64.     if (start_r != -1) {
  65.         q.push({start_r, start_c});
  66.         visited[start_r][start_c] = true;
  67.         dots_kept = 1;
  68.     }
  69.  
  70.     // BFS terminates when queue is empty or dots_kept reaches target_keep
  71.     while (!q.empty() && dots_kept < target_keep) {
  72.         pair<int, int> current = q.front();
  73.         q.pop();
  74.         int r = current.first;
  75.         int c = current.second;
  76.  
  77.         // Explore neighbors
  78.         for (int i = 0; i < 4; ++i) {
  79.             int nr = r + DR[i];
  80.             int nc = c + DC[i];
  81.  
  82.             if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
  83.                 if (grid[nr][nc] == '.' && !visited[nr][nc]) {
  84.  
  85.                     visited[nr][nc] = true;
  86.                     dots_kept++;
  87.  
  88.                     // Enqueue the cell
  89.                     q.push({nr, nc}); 
  90.  
  91.                     if (dots_kept == target_keep) {
  92.                         // Found exactly the required number of connected dots. Stop immediately.
  93.                         goto modification_start; 
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.     }
  99.  
  100. modification_start:
  101.  
  102.     // 3. Modify the grid: Any original dot that was NOT visited by the BFS is turned into 'X'
  103.     for (int i = 0; i < N; ++i) {
  104.         for (int j = 0; j < M; ++j) {
  105.             if (grid[i][j] == '.' && !visited[i][j]) {
  106.                 grid[i][j] = 'X';
  107.             }
  108.         }
  109.     }
  110.  
  111.     // 4. Output the resulting grid
  112.     for (int i = 0; i < N; ++i) {
  113.         cout << grid[i] << "\n";
  114.     }
  115. }
  116.  
  117. int main() {
  118.     solve();
  119.     return 0;
  120. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
5 4 5
#...
#.#.
.#..
...#
.#.#
stdout
copy 
#...
#.#.
X#..
XX.#
X#X#
https://ideone.com/N7uGbO
language:
C++14 (gcc 8.3)
created:
18 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!