Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define ld long double
- #define inf 9e18
- #define v vector
- #define F first
- #define S second
- #define min(a, b) (a < b ? a : b)
- #define max(a, b) (a > b ? a : b)
- int n, m;
- v<v<char>> a;
- v<v<bool>> used;
- v<pair<int, int>> coords;
- int ok_path = -1;
- string path;
- void bfs_find(int x, int y, v<pair<int, int>> &coords) {
- queue<pair<int, int>> q, q1;
- char c = a[x][y];
- q.push({x, y});
- while (!q.empty()) {
- int i = q.front().F, j = q.front().S;
- if (i + 1 < n && !used[i + 1][j] && a[i + 1][j] == c) q.push({i + 1, j});
- if (i - 1 >= 0 && !used[i - 1][j] && a[i - 1][j] == c) q.push({i - 1, j});
- if (j + 1 < m && !used[i][j + 1] && a[i][j + 1] == c) q.push({i, j + 1});
- if (j - 1 >= 0 && !used[i][j - 1] && a[i][j - 1] == c) q.push({i, j - 1});
- // q1 = q;
- // for (int u = 0; u < q.size(); u++) {
- // cout << q1.front().F + 1 << " " << q1.front().S + 1 << " ";
- // q1.pop();
- // }
- // cout << "\n";
- used[i][j] = true;
- coords.push_back({i, j});
- q.pop();
- }
- }
- bool can(int move, pair<int, int> begin, v<pair<int, int>> c) {
- int dx = begin.F - c[0].F, dy = begin.S - c[0].S;
- for (int i = 0; i < c.size(); i++) {
- c[i].F += dx;
- c[i].S += dy;
- }
- if (move == 1 && c[0].F == 0) return false;
- for (int i = 0; i < c.size(); i++) {
- if (move == 1) c[i].F -= 1;
- if (move == 2) c[i].S -= 1;
- if (move == 3) c[i].S += 1;
- }
- bool ok = true;
- for (int i = 0; i < c.size(); i++) {
- if (c[i].F >= n || c[i].S >= m || c[i].S < 0 || a[c[i].F][c[i].S] != '.') {
- ok = false;
- break;
- }
- }
- if (!ok) return false;
- return true;
- }
- void dfs(pair<int, int> begin, string p) {
- if (used[begin.F][begin.S]) return;
- if (begin.F == 0) {
- ok_path = begin.S;
- path = p;
- return;
- }
- used[begin.F][begin.S] = true;
- if (ok_path == -1 && can(1, begin, coords)) dfs({begin.F - 1, begin.S}, "D" + p);
- if (ok_path == -1 && can(2, begin, coords)) dfs({begin.F, begin.S - 1}, "R" + p);
- if (ok_path == -1 && can(3, begin, coords)) dfs({begin.F, begin.S + 1}, "L" + p);
- // 1 - UP, 2 - LEFT, 3 - RIGHT
- }
- signed main(signed argc, char* argv[]) {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- // cout.setf(ios::fixed);
- // cout.precision(6);
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- cin >> n >> m;
- a.resize(n, v<char> ('.'));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cin >> a[i][j];
- }
- }
- v<v<pair<int, int>>> figures;
- used.resize(n, v<bool> (m, false));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (a[i][j] == '.' || used[i][j]) continue;
- used[i][j] = true;
- v<pair<int, int>> coord;
- bfs_find(i, j, coord);
- // for (int k = 0; k < coord.size(); k++) {
- // cout << coord[k].F + 1 << " " << coord[k].S + 1 << " ";
- // }
- // cout << "\n";
- sort(coord.begin(), coord.end());
- figures.push_back(coord);
- }
- }
- v<pair<int, string>> ans;
- while (figures.size()) {
- bool ersd = false;
- for (int i = 0; i < figures.size(); i++) {
- used.clear();
- used.resize(n, v<bool> (m, false));
- char symbol = a[figures[i][0].F][figures[i][0].S];
- for (int k = 0; k < figures[i].size(); k++) {
- a[figures[i][k].F][figures[i][k].S] = '.';
- }
- coords = figures[i];
- ok_path = -1;
- path = "";
- dfs(figures[i][0], "S");
- if (ok_path == -1) {
- for (int k = 0; k < figures[i].size(); k++) {
- a[figures[i][k].F][figures[i][k].S] = symbol;
- }
- } else {
- ans.push_back({ok_path, path});
- figures.erase(figures.begin() + i);
- ersd = true;
- }
- }
- if (!ersd) {
- cout << -1;
- return 0;
- }
- }
- cout << ans.size() << "\n";
- for (int i = ans.size() - 1; i >= 0; i--) {
- cout << ans[i].F + 1 << " " << ans[i].S << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement