# antitetris

Sep 28th, 2022
838
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. #define int long long
6. #define ld long double
7. #define inf 9e18
8. #define v vector
9. #define F first
10. #define S second
11. #define min(a, b) (a < b ? a : b)
12. #define max(a, b) (a > b ? a : b)
13.
14.
15. int n, m;
16. v<v<char>> a;
17. v<v<bool>> used;
18. v<pair<int, int>> coords;
19. int ok_path = -1;
20. string path;
21.
22. void bfs_find(int x, int y, v<pair<int, int>> &coords) {
23.     queue<pair<int, int>> q, q1;
24.     char c = a[x][y];
25.     q.push({x, y});
26.     while (!q.empty()) {
27.         int i = q.front().F, j = q.front().S;
28.         if (i + 1 < n && !used[i + 1][j] && a[i + 1][j] == c) q.push({i + 1, j});
29.         if (i - 1 >= 0 && !used[i - 1][j] && a[i - 1][j] == c) q.push({i - 1, j});
30.         if (j + 1 < m && !used[i][j + 1] && a[i][j + 1] == c) q.push({i, j + 1});
31.         if (j - 1 >= 0 && !used[i][j - 1] && a[i][j - 1] == c) q.push({i, j - 1});
32. //        q1 = q;
33. //        for (int u = 0; u < q.size(); u++) {
34. //            cout << q1.front().F + 1 << " " << q1.front().S + 1 << "  ";
35. //            q1.pop();
36. //        }
37. //        cout << "\n";
38.         used[i][j] = true;
39.         coords.push_back({i, j});
40.         q.pop();
41.     }
42. }
43.
44. bool can(int move, pair<int, int> begin, v<pair<int, int>> c) {
45.     int dx = begin.F - c[0].F, dy = begin.S - c[0].S;
46.     for (int i = 0; i < c.size(); i++) {
47.         c[i].F += dx;
48.         c[i].S += dy;
49.     }
50.
51.     if (move == 1 && c[0].F == 0) return false;
52.     for (int i = 0; i < c.size(); i++) {
53.         if (move == 1) c[i].F -= 1;
54.         if (move == 2) c[i].S -= 1;
55.         if (move == 3) c[i].S += 1;
56.     }
57.     bool ok = true;
58.     for (int i = 0; i < c.size(); i++) {
59.         if (c[i].F >= n || c[i].S >= m || c[i].S < 0 || a[c[i].F][c[i].S] != '.') {
60.             ok = false;
61.             break;
62.         }
63.     }
64.     if (!ok) return false;
65.     return true;
66. }
67.
68. void dfs(pair<int, int> begin, string p) {
69.     if (used[begin.F][begin.S]) return;
70.
71.     if (begin.F == 0) {
72.         ok_path = begin.S;
73.         path = p;
74.         return;
75.     }
76.     used[begin.F][begin.S] = true;
77.
78.     if (ok_path == -1 && can(1, begin, coords)) dfs({begin.F - 1, begin.S}, "D" + p);
79.     if (ok_path == -1 && can(2, begin, coords)) dfs({begin.F, begin.S - 1}, "R" + p);
80.     if (ok_path == -1 && can(3, begin, coords)) dfs({begin.F, begin.S + 1}, "L" + p);
81. //    1 - UP, 2 - LEFT, 3 - RIGHT
82. }
83.
84. signed main(signed argc, char* argv[]) {
85.     ios_base::sync_with_stdio(false);
86.     cin.tie(NULL);
87. //    cout.setf(ios::fixed);
88. //    cout.precision(6);
89. //    freopen("input.txt", "r", stdin);
90. //    freopen("output.txt", "w", stdout);
91.
92.     cin >> n >> m;
93.     a.resize(n, v<char> ('.'));
94.     for (int i = 0; i < n; i++) {
95.         for (int j = 0; j < m; j++) {
96.             cin >> a[i][j];
97.         }
98.     }
99.     v<v<pair<int, int>>> figures;
100.     used.resize(n, v<bool> (m, false));
101.     for (int i = 0; i < n; i++) {
102.         for (int j = 0; j < m; j++) {
103.             if (a[i][j] == '.' || used[i][j]) continue;
104.             used[i][j] = true;
105.             v<pair<int, int>> coord;
106.             bfs_find(i, j, coord);
107. //            for (int k = 0; k < coord.size(); k++) {
108. //                cout << coord[k].F + 1 << " " << coord[k].S + 1 << "  ";
109. //            }
110. //            cout << "\n";
111.             sort(coord.begin(), coord.end());
112.             figures.push_back(coord);
113.         }
114.     }
115.
116.     v<pair<int, string>> ans;
117.     while (figures.size()) {
118.         bool ersd = false;
119.         for (int i = 0; i < figures.size(); i++) {
120.             used.clear();
121.             used.resize(n, v<bool> (m, false));
122.             char symbol = a[figures[i][0].F][figures[i][0].S];
123.             for (int k = 0; k < figures[i].size(); k++) {
124.                 a[figures[i][k].F][figures[i][k].S] = '.';
125.             }
126.             coords = figures[i];
127.             ok_path = -1;
128.             path = "";
129.             dfs(figures[i][0], "S");
130.             if (ok_path == -1) {
131.                 for (int k = 0; k < figures[i].size(); k++) {
132.                     a[figures[i][k].F][figures[i][k].S] = symbol;
133.                 }
134.             } else {
135.                 ans.push_back({ok_path, path});
136.                 figures.erase(figures.begin() + i);
137.                 ersd = true;
138.             }
139.
140.         }
141.         if (!ersd) {
142.             cout << -1;
143.             return 0;
144.         }
145.     }
146.
147.     cout << ans.size() << "\n";
148.     for (int i = ans.size() - 1; i >= 0; i--) {
149.         cout << ans[i].F + 1 << " " << ans[i].S << "\n";
150.     }
151.
152.     return 0;
153. }