#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define fo(i, b) for (int i = 0; i < (b); ++i) #define F first #define S second #define MP make_pair typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; enum class dir { l, r, u, d }; dir bounce(char typ, dir d) { if (typ == '/') { switch (d) { case dir::l: return dir::d; case dir::r: return dir::u; case dir::u: return dir::r; case dir::d: return dir::l; } } if (typ == '\\') { switch (d) { case dir::l: return dir::u; case dir::r: return dir::d; case dir::u: return dir::l; case dir::d: return dir::r; } } return d; } dir rev(dir d) { switch (d) { case dir::l: return dir::r; case dir::r: return dir::l; case dir::u: return dir::d; case dir::d: return dir::u; } } short w, h; vector<string> maze; struct state { short x, y; dir d; state step() { switch (d) { case dir::l: return {x - 1, y, d}; case dir::r: return {x + 1, y, d}; case dir::u: return {x, y - 1, d}; case dir::d: return {x, y + 1, d}; } } ll enc() { return ll(d) + ll(x) * 4 + ll(y) * w * 4; } }; bool bounds(short x, short y) { return x >= 0 && y >= 0 && x < w && y <= h; } ll count() { return w * h * 4; } vector<ll> bounce_time; ll bounce_calc(state s) { if (!bounds(s.x, s.y)) return -INT32_MAX; if (bounce_time[s.enc()] != -INT32_MAX - 1) return bounce_time[s.enc()]; if (maze[s.y][s.x] == '#') { bounce_time[s.enc()] = 0; return 0; } if (maze[s.y][s.x] == '.') { ll ans = bounce_calc(s.step()) + 1; bounce_time[s.enc()] = ans; return ans; } s.d = bounce(maze[s.y][s.x], s.d); ll ans = bounce_calc(s.step()) + 1; bounce_time[s.enc()] = ans; return ans; } struct score { ll dests = INT32_MAX; ll time = INT32_MAX; state prev; }; vector<score> scores; signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cin >> h >> w; maze.resize(h); for (auto &s : maze) cin >> s; short sx, sy; fo(x, w) fo(y, h) { if (maze[y][x] == 'S') { sx = x; sy = y; maze[y][x] = '.'; } } bounce_time.resize(count(), -INT32_MAX - 1); scores.resize(count(), {}); deque<pair<state, score>> q; q.push_back(MP(state{sx, sy, dir::l}, score{0, 0, {}})); q.push_back(MP(state{sx, sy, dir::r}, score{0, 0, {}})); q.push_back(MP(state{sx, sy, dir::u}, score{0, 0, {}})); q.push_back(MP(state{sx, sy, dir::d}, score{0, 0, {}})); std::vector<pair<state, score>> path; while (!q.empty()) { auto [s, sc] = q.front(); q.pop_front(); if (!bounds(s.x, s.y)) { path.push_back(MP(s, sc)); s = sc.prev; while (true) { path.push_back(MP(s, scores[s.enc()])); if (s.x == sx && s.y == s.y) break; s = scores[s.enc()].prev; } break; } if (scores[s.enc()].dests != INT32_MAX) continue; scores[s.enc()] = sc; if (maze[s.y][s.x] == '#') { q.push_front(MP(state{s.x, s.y, rev(s.d)}.step(), score{sc.dests, sc.time, s})); } else if (maze[s.y][s.x] == '.') { q.push_front(MP(state{s.x, s.y, s.d}.step(), score{sc.dests, sc.time + 1, s})); } else { q.push_front(MP(state{s.x, s.y, bounce(maze[s.y][s.x], s.d)}.step(), score{sc.dests, sc.time + 1, s})); q.push_back(MP(state{s.x, s.y, s.d}.step(), score{sc.dests + 1, sc.time + 1, s})); ll tm = bounce_calc(state{s.x, s.y, rev(s.d)}); if (tm >= 0) q.push_back(MP(state{s.x, s.y, rev(bounce(maze[s.y][s.x], s.d))}.step(), score{sc.dests + 1, sc.time + 2 * tm, s})); } } if (path.size() == 0) { cout << "NO\n"; return 0; } cout << "YES\n"; reverse(all(path)); switch (path[0].F.d) { case dir::l: cout << "L\n"; break; case dir::r: cout << "R\n"; break; case dir::u: cout << "U\n"; break; case dir::d: cout << "D\n"; break; } vector<tuple<ll, ll, ll>> res; fo(i, sz(path) - 1) { if (path[i + 1].S.dests > path[i].S.dests) { res.push_back({path[i + 1].S.time, path[i].F.y + 1, path[i].F.x + 1}); } } cout << sz(res) << '\n'; for (auto [a, b, c] : res) cout << a << ' ' << b << ' ' << c << '\n'; }