Advertisement
archen2019

jaanananan

Dec 11th, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <iomanip>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <set>
  7. #include <unordered_set>
  8. #include <vector>
  9. #include <map>
  10. #include <unordered_map>
  11. #include <list>
  12. #include <forward_list>
  13. #include <queue>
  14. #include <deque>
  15. #include <stack>
  16.  
  17. using namespace std;
  18.  
  19. const int INF = 1 << 30;
  20. const int dx[4] = {1, 0, -1, 0};
  21. const int dy[4] = {0, 1, 0, -1};
  22.  
  23. const int MAXL = 40;
  24. const int MAXW = 40;
  25.  
  26. int n, L, W, r0, c0;
  27. char grid[MAXL][MAXW];
  28. bool vis[MAXL][MAXW];
  29.  
  30.  
  31. void solve();
  32. void fill(int, int, char);
  33. bool in_bound(int, int);
  34.  
  35. int main() {
  36.     cin >> n;
  37.     for(int i = 0; i < n; i++) {
  38.         solve();
  39.         memset(grid, 0, sizeof(grid));
  40.         memset(vis, 0, sizeof(vis));
  41.     }
  42.  
  43. }
  44.  
  45. void solve() {
  46.     // read in constant values
  47.     cin >> L >> W >> r0 >> c0;
  48.     // make vector to store trees
  49.     vector< pair< int, int > > trees;
  50.     // read in grid
  51.     for(int i = 0; i < L; i++) {
  52.         for(int j = 0; j < W; j++) {
  53.             cin >> grid[i][j];
  54.             if(grid[i][j] == 'T') {
  55.                 trees.push_back(make_pair(i, j));
  56.             }
  57.         }
  58.     }
  59.     // convert to normal 1x1 floodfill, makes fake trees
  60.     for(vector< pair <int, int> >::iterator it = trees.begin(); it != trees.end(); ++it) {
  61.         fill(it->first, it->second, 't');
  62.     }
  63.     // prevent from reaching edges
  64.     for(int i = 0; i < L; i++) {
  65.         if(grid[i][0] != 'T') grid[i][0] = 't';
  66.         if(grid[i][W - 1] != 'T') grid[i][W - 1] = 't';
  67.     }
  68.     for(int j = 0; j < W; j++) {
  69.         if(grid[0][j] != 'T') grid[0][j] = 't';
  70.         if(grid[L - 1][j] != 'T') grid[L - 1][j] = 't';
  71.     }
  72.     // initialize bfs queue
  73.     queue< pair< int, int > > bfs;
  74.     // push starting position
  75.     bfs.push(make_pair(r0, c0));
  76.     vis[r0][c0] = 1;
  77.     // start bfs floodfill
  78.     while(!bfs.empty()) {
  79.         // read pair at front of queue and pop
  80.         int r = bfs.front().first;
  81.         int c = bfs.front().second;
  82.         bfs.pop();
  83.         // iterates in all four directions
  84.         for(int i = 0; i < 4; i++) {
  85.             int nr = r + dx[i];
  86.             int nc = c + dy[i];
  87.             if(in_bound(nr, nc) && !vis[nr][nc] && grid[nr][nc] == '.') {
  88.                 bfs.push(make_pair(nr, nc));
  89.                 vis[nr][nc] = 1;
  90.             }
  91.         }
  92.     }
  93.     // marks as cut
  94.     for(int i = 0; i < L; i++) {
  95.         for(int j = 0; j < W; j++) {
  96.             if(vis[i][j]) {
  97.                 grid[i][j] = 'C';
  98.                 fill(i, j, 'C');
  99.             }
  100.         }
  101.     }
  102.     // unmarks fake trees
  103.     for(int i = 0; i < L; i++) {
  104.         for(int j = 0; j < W; j++) {
  105.             if(grid[i][j] == 't') grid[i][j] = '.';
  106.         }
  107.     }
  108.     // print final grid
  109.     cout << endl;
  110.     for(int i = 0; i < L; i++) {
  111.         for(int j = 0; j < W - 1; j++) {
  112.             cout << grid[i][j] << " ";
  113.         }
  114.         cout << grid[i][W - 1] << endl;
  115.     }
  116.  
  117. }
  118. // fills 3x3 grid around center square with same char
  119. void fill(int r, int c, char ch) {
  120.     for(int i = -1; i <= 1; i++) {
  121.         for(int j = -1; j <= 1; j++) {
  122.             if(in_bound(r + i, c + j)) {
  123.                 if(ch == 'C' || (ch == 't' && grid[r + i][c + j] == '.')) {
  124.                     grid[r + i][c + j] = ch;
  125.                 }
  126.             }
  127.         }
  128.     }
  129. }
  130. // checks if grid value is in the grid
  131. bool in_bound(int r, int c) {
  132.     if(r < 0 || r >= L || c < 0 || c >= W) return false;
  133.     return true;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement