Submission

PPPPPPP

Score: 100

User: Nathlol2

Problemset: Sirabyrinth 1

Language: cpp

Time: 0.003 second

Submitted On: 2024-11-30 21:23:37

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
char dir[4] = {'R', 'L', 'D', 'U'};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    pair<int, int> start;
    pair<int, int> edge;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') {
                start = {i, j};
            }
        }
    }
    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<vector<int>> tid(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    q.push(start);
    dist[start.first][start.second] = 0;
    visited[start.first][start.second] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == 0 || x == n - 1 || y == 0 || y == m - 1 && make_pair(x, y) != start) {
            edge = {x, y};
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != '#') {
                visited[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
                tid[nx][ny] = i;
                q.push({nx, ny});
            }
        }
    }
    cout << dist[edge.first][edge.second] << '\n';
    string path = "";
    int x = edge.first, y = edge.second;
    while (make_pair(x, y) != start) {
        int d = tid[x][y];
        path += dir[d];
        x -= dx[d];
        y -= dy[d];
    }
    reverse(path.begin(), path.end());
    cout << path;
}