Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <unordered_set>
- #include <vector>
- #include <map>
- #include <unordered_map>
- #include <list>
- #include <forward_list>
- #include <queue>
- #include <deque>
- #include <stack>
- using namespace std;
- const int INF = 1 << 30;
- const int dx[4] = {1, 0, -1, 0};
- const int dy[4] = {0, 1, 0, -1};
- const int MAXL = 40;
- const int MAXW = 40;
- int n, L, W, r0, c0;
- char grid[MAXL][MAXW];
- bool vis[MAXL][MAXW];
- void solve();
- void fill(int, int, char);
- bool in_bound(int, int);
- int main() {
- cin >> n;
- for(int i = 0; i < n; i++) {
- solve();
- memset(grid, 0, sizeof(grid));
- memset(vis, 0, sizeof(vis));
- }
- }
- void solve() {
- // read in constant values
- cin >> L >> W >> r0 >> c0;
- // make vector to store trees
- vector< pair< int, int > > trees;
- // read in grid
- for(int i = 0; i < L; i++) {
- for(int j = 0; j < W; j++) {
- cin >> grid[i][j];
- if(grid[i][j] == 'T') {
- trees.push_back(make_pair(i, j));
- }
- }
- }
- // convert to normal 1x1 floodfill, makes fake trees
- for(vector< pair <int, int> >::iterator it = trees.begin(); it != trees.end(); ++it) {
- fill(it->first, it->second, 't');
- }
- // prevent from reaching edges
- for(int i = 0; i < L; i++) {
- if(grid[i][0] != 'T') grid[i][0] = 't';
- if(grid[i][W - 1] != 'T') grid[i][W - 1] = 't';
- }
- for(int j = 0; j < W; j++) {
- if(grid[0][j] != 'T') grid[0][j] = 't';
- if(grid[L - 1][j] != 'T') grid[L - 1][j] = 't';
- }
- // initialize bfs queue
- queue< pair< int, int > > bfs;
- // push starting position
- bfs.push(make_pair(r0, c0));
- vis[r0][c0] = 1;
- // start bfs floodfill
- while(!bfs.empty()) {
- // read pair at front of queue and pop
- int r = bfs.front().first;
- int c = bfs.front().second;
- bfs.pop();
- // iterates in all four directions
- for(int i = 0; i < 4; i++) {
- int nr = r + dx[i];
- int nc = c + dy[i];
- if(in_bound(nr, nc) && !vis[nr][nc] && grid[nr][nc] == '.') {
- bfs.push(make_pair(nr, nc));
- vis[nr][nc] = 1;
- }
- }
- }
- // marks as cut
- for(int i = 0; i < L; i++) {
- for(int j = 0; j < W; j++) {
- if(vis[i][j]) {
- grid[i][j] = 'C';
- fill(i, j, 'C');
- }
- }
- }
- // unmarks fake trees
- for(int i = 0; i < L; i++) {
- for(int j = 0; j < W; j++) {
- if(grid[i][j] == 't') grid[i][j] = '.';
- }
- }
- // print final grid
- cout << endl;
- for(int i = 0; i < L; i++) {
- for(int j = 0; j < W - 1; j++) {
- cout << grid[i][j] << " ";
- }
- cout << grid[i][W - 1] << endl;
- }
- }
- // fills 3x3 grid around center square with same char
- void fill(int r, int c, char ch) {
- for(int i = -1; i <= 1; i++) {
- for(int j = -1; j <= 1; j++) {
- if(in_bound(r + i, c + j)) {
- if(ch == 'C' || (ch == 't' && grid[r + i][c + j] == '.')) {
- grid[r + i][c + j] = ch;
- }
- }
- }
- }
- }
- // checks if grid value is in the grid
- bool in_bound(int r, int c) {
- if(r < 0 || r >= L || c < 0 || c >= W) return false;
- return true;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement