CSES - Aalto Competitive Programming 2024 - wk2 - Mon - Results
Submission details
Task:Abandoned warehouse
Sender:odanobunaga8199
Submission time:2024-09-09 16:50:44 +0300
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.09 sdetails
#8ACCEPTED0.07 sdetails
#9ACCEPTED0.21 sdetails
#10ACCEPTED0.21 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13--details
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.35 sdetails

Code

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

struct Position {
    int x, y;
    string path;
};

bool isValid(int x, int y, int n, int m, vector<string>& warehouse, vector<vector<bool>>& visited) {
    return x >= 0 && x < n && y >= 0 && y < m && warehouse[x][y] != '#' && !visited[x][y];
}

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

    for (int i = 0; i < n; ++i) {
        cin >> warehouse[i];
        for (int j = 0; j < m; ++j) {
            if (warehouse[i][j] == 'A') {
                start = {i, j};
            } else if (warehouse[i][j] == 'B') {
                end = {i, j};
            }
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<Position> q;
    q.push({start.first, start.second, ""});
    visited[start.first][start.second] = true;

    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    char moves[4] = {'U', 'D', 'L', 'R'};

    while (!q.empty()) {
        Position current = q.front();
        q.pop();

        if (current.x == end.first && current.y == end.second) {
            cout << "YES" << endl;
            cout << current.path.length() << endl;
            cout << current.path << endl;
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            int newX = current.x + directions[i][0];
            int newY = current.y + directions[i][1];
            if (isValid(newX, newY, n, m, warehouse, visited)) {
                visited[newX][newY] = true;
                q.push({newX, newY, current.path + moves[i]});
            }
        }
    }

    cout << "NO" << endl;
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
10 10
##.A######
#.##.##.##
#####..###
.#########
...

correct output
NO

user output
NO

Test 2

Verdict: ACCEPTED

input
10 10
B#..##.#..
#....A##..
#.....#..#
.#......#.
...

correct output
NO

user output
NO

Test 3

Verdict: ACCEPTED

input
10 10
...#..A.#.
....B...##
...#......
..........
...

correct output
YES
3
LLD

user output
YES
3
DLL

Test 4

Verdict: ACCEPTED

input
10 10
.#........
..........
..........
........#.
...

correct output
YES
1
R

user output
YES
1
R

Test 5

Verdict: ACCEPTED

input
10 10
..........
..........
..........
..........
...

correct output
YES
3
RDD

user output
YES
3
DDR

Test 6

Verdict: ACCEPTED

input
1000 1000
##.###..######.#########.###.#...

correct output
NO

user output
NO

Test 7

Verdict: ACCEPTED

input
1000 1000
####.#.###....#.......##.##.#....

correct output
YES
626
LLLDDRDDDDLDLDDLLLLLDDDDLLDLDL...

user output
YES
626
LLLDDRDDDDDDLLDDLLDDDLDDLLLDDL...
Truncated

Test 8

Verdict: ACCEPTED

input
1000 1000
....#.##......#....#......#......

correct output
YES
364
LULULLULLLULLLLLUULLLLUUULLLLL...

user output
YES
364
UUUUUULUUUUUUUUUUULLLUUUULLUUU...
Truncated

Test 9

Verdict: ACCEPTED

input
1000 1000
.................#......#........

correct output
YES
1003
LLLLLLLLLLLLLLLLLLLLLLLLLDLLLL...

user output
YES
1003
DDDDDDDDDDDDDDDDDLDDDDDDDDDDDD...
Truncated

Test 10

Verdict: ACCEPTED

input
1000 1000
.................................

correct output
YES
947
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

user output
YES
947
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU...
Truncated

Test 11

Verdict: ACCEPTED

input
1000 3
A#B
.#.
.#.
.#.
...

correct output
YES
2000
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
YES
2000
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...
Truncated

Test 12

Verdict: ACCEPTED

input
3 1000
A................................

correct output
YES
2000
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
YES
2000
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 13

Verdict:

input
999 999
A#...#...#...#...#...#...#...#...

correct output
YES
499998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 14

Verdict: ACCEPTED

input
1 3
A.B

correct output
YES
2
RR

user output
YES
2
RR

Test 15

Verdict: ACCEPTED

input
2 2
##
AB

correct output
YES
1
R

user output
YES
1
R

Test 16

Verdict: ACCEPTED

input
1000 1000
A................................

correct output
YES
1998
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
YES
1998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...
Truncated