260382026-03-13 17:27:06xxxLegközelebbi mezőkcpp17Elfogadva 100/100388ms59956 KiB
#include <bits/stdc++.h>
using namespace std;

vector<string> s;
vector<vector<int> > A, B, C;

int n, m;

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

bool check (int i, int j) {
    if (i >= n || i < 0 || j >= m || j < 0) {
        return 0;
    }
    return 1;
}

int main() {
    cin >> n >> m;
    s.assign(n, "");
    A.assign(n, vector<int>(m, 0));
    B.assign(n, vector<int>(m, 0));
    C.assign(n, vector<int>(m, 5000));
    int ai, aj, bi, bj;
    for(int i = 0; i < n; i++) {
        cin >> s[i];
        for(int j = 0; j < m; j++) {
            if (s[i][j] == 'A') {
                ai = i;
                aj = j;
            } else if (s[i][j] == 'B') {
                bi = i;
                bj = j;
            }
        }
    }

    queue<pair<int, int> > q;
    queue<pair<int, int> > qq;
    q.push(make_pair(ai, aj));
    qq.push(make_pair(ai, aj));
    A[ai][aj] = 1;
    C[ai][aj] = 0;

    while(!q.empty()) {
        auto[x, y] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            if (check(x+dx[i], y+dy[i]) && A[x+dx[i]][y+dy[i]] == 0) {
                if (s[x+dx[i]][y+dy[i]] != '#') {
                    A[x+dx[i]][y+dy[i]] = 1;
                    C[x+dx[i]][y+dy[i]] = 0;
                    qq.push(make_pair(x+dx[i], y+dy[i]));
                    q.push(make_pair(x+dx[i], y+dy[i]));
                } else {
                    A[x+dx[i]][y+dy[i]] = 2;
                }
            }
        }

    }


    q.push(make_pair(bi, bj));
    B[bi][bj] = 1;

    while(!q.empty()) {
        auto[x, y] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            if (check(x+dx[i], y+dy[i]) && B[x+dx[i]][y+dy[i]] == 0) {
                if (s[x+dx[i]][y+dy[i]] != '#') {
                    B[x+dx[i]][y+dy[i]] = 1;
                    q.push(make_pair(x+dx[i], y+dy[i]));
                } else {
                    B[x+dx[i]][y+dy[i]] = 2;
                }
            }
        }

    }

/*    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << A[i][j];
        }
        cout << endl;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << B[i][j];
        }
        cout << endl;
    }*/

    int ans = 10000;

    while(!qq.empty()) {
        auto[x, y] = qq.front();
        qq.pop();
        if (B[x][y] == 1) {
            ans = min(ans, C[x][y]);
        }

        for(int i = 0; i < 4; i++) {
            if (check(x+dx[i], y+dy[i]) && C[x+dx[i]][y+dy[i]] > C[x][y]+1) {
                C[x+dx[i]][y+dy[i]] = C[x][y]+1;
                qq.push(make_pair(x+dx[i], y+dy[i]));
            }
        }
    }


    cout << ans << endl;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
subtask210/10
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva2ms316 KiB
9Elfogadva2ms316 KiB
10Elfogadva2ms316 KiB
11Elfogadva2ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva2ms564 KiB
14Elfogadva2ms324 KiB
subtask320/20
15Elfogadva14ms2688 KiB
16Elfogadva16ms3400 KiB
17Elfogadva197ms30516 KiB
18Elfogadva131ms19252 KiB
19Elfogadva13ms2868 KiB
20Elfogadva16ms3396 KiB
21Elfogadva14ms3424 KiB
22Elfogadva150ms28204 KiB
23Elfogadva16ms3312 KiB
24Elfogadva171ms29108 KiB
subtask420/20
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva64ms12596 KiB
29Elfogadva67ms11572 KiB
30Elfogadva48ms10036 KiB
31Elfogadva54ms11324 KiB
32Elfogadva43ms9524 KiB
33Elfogadva64ms12768 KiB
34Elfogadva67ms13556 KiB
35Elfogadva48ms9052 KiB
36Elfogadva59ms12140 KiB
37Elfogadva61ms12148 KiB
38Elfogadva114ms23348 KiB
39Elfogadva291ms55092 KiB
40Elfogadva307ms55088 KiB
41Elfogadva289ms55048 KiB
42Elfogadva270ms55092 KiB
subtask550/50
43Elfogadva1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva1ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva2ms316 KiB
48Elfogadva2ms316 KiB
49Elfogadva2ms316 KiB
50Elfogadva2ms316 KiB
51Elfogadva1ms316 KiB
52Elfogadva2ms564 KiB
53Elfogadva2ms324 KiB
54Elfogadva14ms2688 KiB
55Elfogadva16ms3400 KiB
56Elfogadva197ms30516 KiB
57Elfogadva131ms19252 KiB
58Elfogadva13ms2868 KiB
59Elfogadva16ms3396 KiB
60Elfogadva14ms3424 KiB
61Elfogadva150ms28204 KiB
62Elfogadva16ms3312 KiB
63Elfogadva171ms29108 KiB
64Elfogadva64ms12596 KiB
65Elfogadva67ms11572 KiB
66Elfogadva48ms10036 KiB
67Elfogadva54ms11324 KiB
68Elfogadva43ms9524 KiB
69Elfogadva64ms12768 KiB
70Elfogadva67ms13556 KiB
71Elfogadva48ms9052 KiB
72Elfogadva59ms12140 KiB
73Elfogadva61ms12148 KiB
74Elfogadva114ms23348 KiB
75Elfogadva291ms55092 KiB
76Elfogadva307ms55088 KiB
77Elfogadva289ms55048 KiB
78Elfogadva270ms55092 KiB
79Elfogadva72ms12204 KiB
80Elfogadva70ms13108 KiB
81Elfogadva56ms9964 KiB
82Elfogadva50ms9268 KiB
83Elfogadva63ms11512 KiB
84Elfogadva90ms13676 KiB
85Elfogadva56ms10112 KiB
86Elfogadva46ms8756 KiB
87Elfogadva71ms13276 KiB
88Elfogadva83ms13560 KiB
89Elfogadva63ms9124 KiB
90Elfogadva76ms13336 KiB
91Elfogadva85ms14124 KiB
92Elfogadva71ms12704 KiB
93Elfogadva79ms12728 KiB
94Elfogadva92ms13644 KiB
95Elfogadva74ms13108 KiB
96Elfogadva71ms13408 KiB
97Elfogadva72ms13768 KiB
98Elfogadva50ms9780 KiB
99Elfogadva241ms39476 KiB
100Elfogadva317ms45876 KiB
101Elfogadva79ms12824 KiB
102Elfogadva238ms42036 KiB
103Elfogadva354ms40900 KiB
104Elfogadva349ms59232 KiB
105Elfogadva314ms57652 KiB
106Elfogadva388ms59956 KiB
107Elfogadva349ms57140 KiB