CSES - Aalto Competitive Programming 2024 - wk2 - Mon - Results
Submission details
Task:Abandoned warehouse
Sender:Rasse
Submission time:2024-09-09 16:56:28 +0300
Language:C++11
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#40.00 sdetails
#50.00 sdetails
#6ACCEPTED0.03 sdetails
#70.07 sdetails
#80.07 sdetails
#90.09 sdetails
#100.04 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.09 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#160.16 sdetails

Compiler report

input/code.cpp: In function 'bool dfs(int, int, std::vector<int>&, std::vector<std::vector<char> >&)':
input/code.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (x < map[y].size() - 1 && map[y][x+1] != '#' && dfs(x+1, y, resultVec, map))
      |         ~~^~~~~~~~~~~~~~~~~~~
input/code.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if (y < map.size() - 1 && map[y+1][x] != '#' && dfs(x, y+1, resultVec, map))
      |         ~~^~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:45:9: warning: variable 'endX' set but not used [-Wunused-but-set-variable]
   45 |     int endX, endY = 0;
      |         ^~~~
input/code.cpp:45:15: warning: variable 'endY' set but not used [-Wunused-but-set-variable]...

Code

// Online C++ compiler to run C++ program online
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool dfs(int x, int y, vector<int>& resultVec, vector<vector<char>>& map)
{
    if (map[y][x] == 'B')
        return true;
    
    map[y][x] = '#';
    if (y > 0 && map[y-1][x] != '#' && dfs(x, y - 1, resultVec, map))
    {
        resultVec.push_back('U');
        return true;
    }
    if (x > 0 && map[y][x-1] != '#' && dfs(x-1, y, resultVec, map))
    {
        resultVec.push_back('L');
        return true;
    }
    if (x < map[y].size() - 1 && map[y][x+1] != '#' && dfs(x+1, y, resultVec, map))
    {
        resultVec.push_back('R');
        return true;
    }
    if (y < map.size() - 1 && map[y+1][x] != '#' && dfs(x, y+1, resultVec, map))
    {
        resultVec.push_back('D');
        return true;
    }
    
    return false;
}

int main() {
    // Write C++ code here
    int n, m; // height, width
    std::cin >> n >> m;
    
    vector<vector<char>> map = vector<vector<char>>(n, vector<char>(m, 0));
    int startX, startY = 0;
    int endX, endY = 0;
    for (int y = 0; y < n; y++)
    {
        string line;
        std::cin >> line;
        for (int x = 0; x < m; x++)
        {
            map[y][x] = line[x];
            if (line[x] == 'A')
            {
                startX = x;
                startY = y;
            }
            else if (line[x] == 'B')
            {
                endX = x;
                endY = y;
            }
        }
    }
    
    vector<int> result = vector<int>();
    if (dfs(startX, startY, result, map))
    {
        std::cout << "YES" << std::endl;
        std::cout << result.size() << std::endl;
        for (int i = result.size() - 1; i > -1; i--)
            std::cout << (char)result[i];
        
    }
    else
    {
        std::cout << "NO";
    }
    
    

    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
LLD

Test 4

Verdict:

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

correct output
YES
1
R

user output
YES
73
UUUUUUUULLLLLDLLDRRRURRRDLLDLL...

Test 5

Verdict:

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

correct output
YES
3
RDD

user output
YES
79
UUUUULLLDRRDLLDRRDLLDRRDLLDRRR...

Test 6

Verdict: ACCEPTED

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

correct output
NO

user output
NO

Test 7

Verdict:

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

correct output
YES
626
LLLDDRDDDDLDLDDLLLLLDDDDLLDLDL...

user output
YES
248118
UUUUUUUUUUUUUUUUUUULUUUUUUULLU...

Test 8

Verdict:

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

correct output
YES
364
LULULLULLLULLLLLUULLLLUUULLLLL...

user output
YES
324322
UUUUUULUUUUUUUUUUULLLUUUUURUUR...

Test 9

Verdict:

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

correct output
YES
1003
LLLLLLLLLLLLLLLLLLLLLLLLLDLLLL...

user output
YES
420235
LLULLLLUUUUUUUUUUUUUUUURUUUUUU...

Test 10

Verdict:

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

correct output
YES
947
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

user output
YES
84935
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU...

Test 11

Verdict: ACCEPTED

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

correct output
YES
2000
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
YES
2000
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

Test 12

Verdict: ACCEPTED

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

correct output
YES
2000
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
YES
2000
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

Test 13

Verdict: ACCEPTED

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

correct output
YES
499998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
YES
499998
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

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:

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

correct output
YES
1998
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
YES
999000
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...