191852025-11-28 14:38:45szilLegközelebbi mezőkcpp17Elfogadva 100/100465ms42492 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 2001;
const int INF = 1e9;

int n, m;

const pair<int, int> DIR[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool is_ok(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= m;
}

int dist[MAXN][MAXN];
char c[MAXN][MAXN];
bool vis1[MAXN][MAXN], vis2[MAXN][MAXN];

void dfs1(int x, int y) {
    vis1[x][y] = 1;
    for (auto [dx, dy] : DIR) {
        int nx = x + dx;
        int ny = y + dy;
        if (is_ok(nx, ny) && !vis1[nx][ny] && c[nx][ny] != '#') {
            dfs1(nx, ny);
        }
    }
}

void dfs2(int x, int y) {
    vis2[x][y] = 1;
    for (auto [dx, dy] : DIR) {
        int nx = x + dx;
        int ny = y + dy;
        if (is_ok(nx, ny) && !vis2[nx][ny] && c[nx][ny] != '#') {
            dfs2(nx, ny);
        }
    }
}

void bfs() {
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis1[i][j]) {
                q.push({i, j});
            } else {
                dist[i][j] = INF;
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (auto [dx, dy] : DIR) {
            int nx = x + dx;
            int ny = y + dy;
            if (is_ok(nx, ny) && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == 'A') {
                dfs1(i, j);
            }
            if (c[i][j] == 'B') {
                dfs2(i, j);
            }
        }
    }
    bfs();
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis2[i][j]) ans = min(ans, dist[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms500 KiB
3Elfogadva1ms316 KiB
subtask210/10
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva3ms1100 KiB
8Elfogadva3ms1220 KiB
9Elfogadva3ms1016 KiB
10Elfogadva3ms1076 KiB
11Elfogadva2ms1076 KiB
12Elfogadva2ms820 KiB
13Elfogadva3ms1076 KiB
14Elfogadva3ms1332 KiB
subtask320/20
15Elfogadva28ms10772 KiB
16Elfogadva29ms12844 KiB
17Elfogadva256ms34428 KiB
18Elfogadva175ms27192 KiB
19Elfogadva27ms11064 KiB
20Elfogadva34ms12764 KiB
21Elfogadva21ms2356 KiB
22Elfogadva215ms16696 KiB
23Elfogadva21ms2100 KiB
24Elfogadva221ms17972 KiB
subtask420/20
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms508 KiB
28Elfogadva97ms13108 KiB
29Elfogadva90ms12864 KiB
30Elfogadva79ms11572 KiB
31Elfogadva90ms16324 KiB
32Elfogadva71ms11664 KiB
33Elfogadva100ms14644 KiB
34Elfogadva101ms15444 KiB
35Elfogadva71ms12556 KiB
36Elfogadva98ms16692 KiB
37Elfogadva96ms16692 KiB
38Elfogadva184ms14384 KiB
39Elfogadva381ms24116 KiB
40Elfogadva404ms24116 KiB
41Elfogadva386ms23952 KiB
42Elfogadva407ms24116 KiB
subtask550/50
43Elfogadva1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva1ms508 KiB
46Elfogadva3ms1100 KiB
47Elfogadva3ms1220 KiB
48Elfogadva3ms1016 KiB
49Elfogadva3ms1076 KiB
50Elfogadva2ms1076 KiB
51Elfogadva2ms820 KiB
52Elfogadva3ms1076 KiB
53Elfogadva3ms1332 KiB
54Elfogadva28ms10772 KiB
55Elfogadva29ms12844 KiB
56Elfogadva256ms34428 KiB
57Elfogadva175ms27192 KiB
58Elfogadva27ms11064 KiB
59Elfogadva34ms12764 KiB
60Elfogadva21ms2356 KiB
61Elfogadva215ms16696 KiB
62Elfogadva21ms2100 KiB
63Elfogadva221ms17972 KiB
64Elfogadva97ms13108 KiB
65Elfogadva90ms12864 KiB
66Elfogadva79ms11572 KiB
67Elfogadva90ms16324 KiB
68Elfogadva71ms11664 KiB
69Elfogadva100ms14644 KiB
70Elfogadva101ms15444 KiB
71Elfogadva71ms12556 KiB
72Elfogadva98ms16692 KiB
73Elfogadva96ms16692 KiB
74Elfogadva184ms14384 KiB
75Elfogadva381ms24116 KiB
76Elfogadva404ms24116 KiB
77Elfogadva386ms23952 KiB
78Elfogadva407ms24116 KiB
79Elfogadva115ms23348 KiB
80Elfogadva112ms20020 KiB
81Elfogadva85ms18484 KiB
82Elfogadva79ms16436 KiB
83Elfogadva97ms19252 KiB
84Elfogadva119ms27956 KiB
85Elfogadva86ms16180 KiB
86Elfogadva78ms17184 KiB
87Elfogadva112ms18740 KiB
88Elfogadva114ms21552 KiB
89Elfogadva81ms16788 KiB
90Elfogadva108ms18520 KiB
91Elfogadva115ms19764 KiB
92Elfogadva109ms16188 KiB
93Elfogadva108ms19120 KiB
94Elfogadva112ms19612 KiB
95Elfogadva115ms20788 KiB
96Elfogadva111ms14132 KiB
97Elfogadva108ms19252 KiB
98Elfogadva78ms15016 KiB
99Elfogadva319ms29748 KiB
100Elfogadva395ms42492 KiB
101Elfogadva109ms18996 KiB
102Elfogadva321ms34624 KiB
103Elfogadva365ms40132 KiB
104Elfogadva456ms37172 KiB
105Elfogadva426ms34100 KiB
106Elfogadva465ms40172 KiB
107Elfogadva441ms33336 KiB