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

Code

#include <bits/stdc++.h>
using namespace std;
const vector<tuple<int, int, char>> directions = {{-1, 0, 'U'}, {1, 0, 'D'}, {0, -1, 'L'}, {0, 1, 'R'}};
bool bfs(const vector<string>& warehouse, pair<int, int> start, pair<int, int> end, vector<vector<bool>>& visited, vector<vector<pair<int, int>>>& parent) {
int n = warehouse.size();
int m = warehouse[0].size();
queue<pair<int, int>> q;
q.push(start);
visited[start.first][start.second] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (make_pair(x, y) == end) return true;
for (const auto& [dx, dy, move] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && warehouse[nx][ny] != '#') {
visited[nx][ny] = true;
q.push({nx, ny});
parent[nx][ny] = {x, y};
}
}
}
return false;
}
int main() {
// Input
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};
if (warehouse[i][j] == 'B') end = {i, j};
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
vector<vector<pair<int, int>>> parent(n, vector<pair<int, int>>(m, {-1, -1}));
if (bfs(warehouse, start, end, visited, parent)) {
cout << "YES\n";
string path;
pair<int, int> current = end;
while (current != start) {
auto [px, py] = parent[current.first][current.second];
for (const auto& [dx, dy, move] : directions) {
if (px + dx == current.first && py + dy == current.second) {
path.push_back(move);
break;
}
}
current = {px, py};
}
reverse(path.begin(), path.end());
cout << path.length() << '\n';
cout << path << '\n';
} else {
cout << "NO\n";
}
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: ACCEPTED

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

correct output
YES
499998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
YES
499998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...
Truncated

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