Advertisement
MegaVerkruzo

Untitled

Sep 16th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. map<pair<int, int>, int> f;
  9.  
  10. void dfs(vector<vector<char>>& a, vector<pair<int, int>>& z, int x, int y, int pred_x, int pred_y) {
  11. if (x == 0 && y == 0) {
  12. return;
  13. }
  14. z.push_back({ x, y });
  15. a[x][y] = 'X';
  16. f[{x, y}] = 1;
  17. if (a[x - 1][y] != 'B' && (pred_x != x - 1 || pred_y != y)) {
  18. if (a[x - 1][y] == 'l') {
  19. dfs(a, z, x - 1, y, x, y);
  20. }
  21. else if (f[{x - 1, y}] == 1) {
  22. int i = z.size() - 1;
  23. while (i >= 0 && (z[i].first != x - 1 || z[i].second != y)) {
  24. a[z[i].first][z[i].second] = '.';
  25. i--;
  26. }
  27. if (i >= 0) {
  28. a[z[i].first][z[i].second] = '.';
  29. }
  30. }
  31. }
  32. if (a[x + 1][y] != 'B' && (pred_x != x + 1 || pred_y != y)) {
  33. if (a[x + 1][y] == 'l') {
  34. dfs(a, z, x + 1, y, x, y);
  35. }
  36. else if (f[{x + 1, y}] == 1) {
  37. int i = z.size() - 1;
  38. while (i >= 0 && (z[i].first != x + 1 || z[i].second != y)) {
  39. a[z[i].first][z[i].second] = '.';
  40. i--;
  41. }
  42. if (i >= 0) {
  43. a[z[i].first][z[i].second] = '.';
  44. }
  45. }
  46. }
  47. if (a[x][y - 1] != 'B' && (pred_x != x || pred_y != y - 1)) {
  48. if (a[x][y - 1] == 'l') {
  49. dfs(a, z, x, y - 1, x, y);
  50. }
  51. else if (f[{x, y - 1}] == 1) {
  52. int i = z.size() - 1;
  53. while (i >= 0 && (z[i].first != x || z[i].second != y - 1)) {
  54. a[z[i].first][z[i].second] = '.';
  55. i--;
  56. }
  57. if (i >= 0) {
  58. a[z[i].first][z[i].second] = '.';
  59. }
  60. }
  61. }
  62. if (a[x][y + 1] != 'B' && (pred_x != x || pred_y != y + 1)) {
  63. if (a[x][y + 1] == 'l') {
  64. dfs(a, z, x, y + 1, x, y);
  65. }
  66. else if (f[{x, y + 1}] == 1) {
  67. int i = z.size() - 1;
  68. while (i >= 0 && (z[i].first != x || z[i].second != y + 1)) {
  69. a[z[i].first][z[i].second] = '.';
  70. i--;
  71. }
  72. if (i >= 0) {
  73. a[z[i].first][z[i].second] = '.';
  74. }
  75. }
  76. }
  77. f[{x, y}] = 0;
  78. z.pop_back();
  79. }
  80.  
  81. int main()
  82. {
  83. int n, m;
  84. cin >> n >> m;
  85. vector<vector<char>> a(n + 2, vector<char>(m + 2, 'B'));
  86. for (int i = 1; i <= n; ++i) {
  87. for (int l = 1; l <= m; ++l) {
  88. cin >> a[i][l];
  89. if (a[i][l] == '.') {
  90. a[i][l] = 'l';
  91. }
  92. }
  93. }
  94. vector<pair<int, int>> z;
  95. for (int i = 1; i <= n; ++i) {
  96. for (int l = 1; l <= m; ++l) {
  97. if (a[i][l] == 'l') {
  98. dfs(a, z, i, l, i, l);
  99. }
  100. }
  101. }
  102. for (int x = 1; x <= n; ++x) {
  103. for (int y = 1; y <= m; ++y) {
  104. cout << a[x][y];
  105. }
  106. cout << "\n";
  107. }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement