Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <map>
- using namespace std;
- map<pair<int, int>, int> f;
- void dfs(vector<vector<char>>& a, vector<pair<int, int>>& z, int x, int y, int pred_x, int pred_y) {
- if (x == 0 && y == 0) {
- return;
- }
- z.push_back({ x, y });
- a[x][y] = 'X';
- f[{x, y}] = 1;
- if (a[x - 1][y] != 'B' && (pred_x != x - 1 || pred_y != y)) {
- if (a[x - 1][y] == 'l') {
- dfs(a, z, x - 1, y, x, y);
- }
- else if (f[{x - 1, y}] == 1) {
- int i = z.size() - 1;
- while (i >= 0 && (z[i].first != x - 1 || z[i].second != y)) {
- a[z[i].first][z[i].second] = '.';
- i--;
- }
- if (i >= 0) {
- a[z[i].first][z[i].second] = '.';
- }
- }
- }
- if (a[x + 1][y] != 'B' && (pred_x != x + 1 || pred_y != y)) {
- if (a[x + 1][y] == 'l') {
- dfs(a, z, x + 1, y, x, y);
- }
- else if (f[{x + 1, y}] == 1) {
- int i = z.size() - 1;
- while (i >= 0 && (z[i].first != x + 1 || z[i].second != y)) {
- a[z[i].first][z[i].second] = '.';
- i--;
- }
- if (i >= 0) {
- a[z[i].first][z[i].second] = '.';
- }
- }
- }
- if (a[x][y - 1] != 'B' && (pred_x != x || pred_y != y - 1)) {
- if (a[x][y - 1] == 'l') {
- dfs(a, z, x, y - 1, x, y);
- }
- else if (f[{x, y - 1}] == 1) {
- int i = z.size() - 1;
- while (i >= 0 && (z[i].first != x || z[i].second != y - 1)) {
- a[z[i].first][z[i].second] = '.';
- i--;
- }
- if (i >= 0) {
- a[z[i].first][z[i].second] = '.';
- }
- }
- }
- if (a[x][y + 1] != 'B' && (pred_x != x || pred_y != y + 1)) {
- if (a[x][y + 1] == 'l') {
- dfs(a, z, x, y + 1, x, y);
- }
- else if (f[{x, y + 1}] == 1) {
- int i = z.size() - 1;
- while (i >= 0 && (z[i].first != x || z[i].second != y + 1)) {
- a[z[i].first][z[i].second] = '.';
- i--;
- }
- if (i >= 0) {
- a[z[i].first][z[i].second] = '.';
- }
- }
- }
- f[{x, y}] = 0;
- z.pop_back();
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- vector<vector<char>> a(n + 2, vector<char>(m + 2, 'B'));
- for (int i = 1; i <= n; ++i) {
- for (int l = 1; l <= m; ++l) {
- cin >> a[i][l];
- if (a[i][l] == '.') {
- a[i][l] = 'l';
- }
- }
- }
- vector<pair<int, int>> z;
- for (int i = 1; i <= n; ++i) {
- for (int l = 1; l <= m; ++l) {
- if (a[i][l] == 'l') {
- dfs(a, z, i, l, i, l);
- }
- }
- }
- for (int x = 1; x <= n; ++x) {
- for (int y = 1; y <= m; ++y) {
- cout << a[x][y];
- }
- cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement