CSES - Datatähti 2022 loppu - Results
Submission details
Task:Sokkelo
Sender:MojoLake
Submission time:2022-01-22 13:48:37 +0200
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED72
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s1, 2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.11 s2details
#5ACCEPTED0.07 s2details
#6ACCEPTED0.05 s2details
#7ACCEPTED0.01 s1, 2details
#8ACCEPTED0.04 s2details
#9ACCEPTED0.04 s2details
#10ACCEPTED0.01 s1, 2details
#11ACCEPTED0.04 s2details
#12ACCEPTED0.01 s1, 2details
#13ACCEPTED0.03 s2details
#14ACCEPTED0.01 s1, 2details
#15ACCEPTED0.03 s2details
#16ACCEPTED0.01 s2details
#17ACCEPTED0.01 s2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:47:24: warning: 'bx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(ay, ax, 0); dfs(by, bx, 1);
                     ~~~^~~~~~~~~~~
input/code.cpp:47:8: warning: 'ay' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(ay, ax, 0); dfs(by, bx, 1);
     ~~~^~~~~~~~~~~
input/code.cpp:47:8: warning: 'ax' may be used uninitialized in this function [-Wmaybe-uninitialized]
input/code.cpp:47:24: warning: 'by' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(ay, ax, 0); dfs(by, bx, 1);
                     ~~~^~~~~~~~~~~

Code

#include <bits/stdc++.h>

#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = (int)1e5;
const int inf = (int)1e8;
bool grid[1000][1000];
bool vis[1000][1000][2];



void dfs(int y, int x, bool b){
    //cout << y << " " << x << "\n";
    vis[y][x][b] = 1;
    if(grid[y+1][x]&&!vis[y+1][x][b])dfs(y+1, x, b);
    if(grid[y-1][x]&&!vis[y-1][x][b])dfs(y-1, x, b);
    if(grid[y][x+1]&&!vis[y][x+1][b])dfs(y, x+1, b);
    if(grid[y][x-1]&&!vis[y][x-1][b])dfs(y, x-1, b);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    int ay, ax, by, bx;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            char c; cin >> c;
            if(c=='#')grid[i][j]=0;
            else grid[i][j] = 1;
            if(c=='A'){
                ay = i;
                ax = j;
            }
            else if(c=='B'){
                by = i;
                bx = j;
            }
        }
    }
    dfs(ay, ax, 0); dfs(by, bx, 1);
    ll closestA[n][m];
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(vis[i][j][0])closestA[i][j]=0;
            else closestA[i][j] = inf;
            //cout << closestA[i][j] << " ";
        }
    }
    for(int i = 1; i < n - 1; ++i){
        for(int j = 1; j < m - 1; ++j){
            if(!vis[i][j][0]){
                closestA[i][j] = min(closestA[i][j], min(closestA[i+1][j], min(closestA[i-1][j], min(closestA[i][j+1], closestA[i][j-1])))+1);
            }
            //cout << closestA[i][j] << " ";
        }
    }
    ll ans = inf;
    for(int i = 1; i < n-1; ++i){
        for(int j = 1; j < m - 1; ++j){
            if(!vis[i][j][1])continue;
            else ans = min(ans, closestA[i][j]);
        }
    }
    if(!ans)cout << "1\n";
    else cout << ans << "\n";



    return 0;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
1

user output
1

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
2

user output
2

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#A.................#
#..................#
#..................#
...

correct output
9

user output
9

Test 4

Group: 2

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 5

Group: 2

Verdict: ACCEPTED

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

correct output
2

user output
2

Test 6

Group: 2

Verdict: ACCEPTED

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

correct output
335

user output
335

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#####.##############
###.....############
##.......###########
...

correct output
10

user output
10

Test 8

Group: 2

Verdict: ACCEPTED

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

correct output
436

user output
436

Test 9

Group: 2

Verdict: ACCEPTED

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

correct output
2

user output
2

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
#B................##
#################.##
#################.##
...

correct output
2

user output
2

Test 11

Group: 2

Verdict: ACCEPTED

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

correct output
2

user output
2

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
##########A#########
##########.#########
##########.#########
...

correct output
2

user output
2

Test 13

Group: 2

Verdict: ACCEPTED

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

correct output
2

user output
2

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
##########A#########
##########.#########
##########.#########
...

correct output
12

user output
12

Test 15

Group: 2

Verdict: ACCEPTED

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

correct output
502

user output
502

Test 16

Group: 2

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 17

Group: 2

Verdict: ACCEPTED

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

correct output
1

user output
1