제출 #1338196

#제출 시각아이디문제언어결과실행 시간메모리
1338196ahmetlbktd4Natjecanje (COCI25_natjecanje)C++20
0 / 110
3 ms1652 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;
    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')
            x1 = i,y1 = j;
        }
    }
    int x2 = -1,y2 = -1;
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            if (i^x2 && j^y2 && a[i][j] == 'X'){
                x2 = i,y2 = j;
                break;
            }
        }
    }
    assert(k==2);
    int d1 = bfs(sx,sy,x1,y1);
    int d2 = bfs(sx,sy,x2,y2);
    int dxy = bfs(x1,y1,x2,y2);
    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...