Submission #1338221

#TimeUsernameProblemLanguageResultExecution timeMemory
1338221ahmetlbktd4Natjecanje (COCI25_natjecanje)C++20
17 / 110
13 ms1692 KiB
#include "bits/stdc++.h"
#define ff first
#define ss second
using namespace std;

const int N = 505;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int n,m,k;
char a[N][N];

int bfs(int sx,int sy,int x,int y){
    queue <pair<int,int>> q;
    vector <vector <int>> d(n,vector<int> (m,-1));
    d[sx][sy] = 0;
    q.push({sx,sy});
    while (!q.empty()){
        int a1 = q.front().ff,b = q.front().ss;  
        q.pop();
        if (a1 == x && b == y)
        return d[x][y];
        for (int i = 0;i < 4;i++){
            int nx = a1+dx[i],ny = b+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
            if (a[nx][ny] == '#')
            continue;
            if (~d[nx][ny])
            continue;
            d[nx][ny] = d[a1][b]+1;
            q.push({nx,ny});
        }
    }
    return d[x][y];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    vector <pair<int,int>> c;
    int sx = -1,sy = -1,x1=-1,y1=-1;
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            cin >> a[i][j];
            if (a[i][j] == 'S')
            sx = i,sy = j;
            if (a[i][j] == 'X')
            c.push_back({i,j});
        }
    }
    assert(k==2);
    int d1 = bfs(sx,sy,c[0].ff,c[0].ss);
    int d2 = bfs(sx,sy,c[1].ff,c[1].ss);
    int dxy = bfs(c[0].ff,c[0].ss,c[1].ff,c[1].ss);
    if (d1 == -1 || d2 == -1){
        cout << "-1\n";return 0;
    }
    cout << min(2*d1+2*d2,d1+d2+dxy) << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...