260382026-03-13 17:27:06xxxLegközelebbi mezőkcpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Accepted1ms316 KiB
3Accepted1ms316 KiB
subtask210/10
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted2ms316 KiB
9Accepted2ms316 KiB
10Accepted2ms316 KiB
11Accepted2ms316 KiB
12Accepted1ms316 KiB
13Accepted2ms564 KiB
14Accepted2ms324 KiB
subtask320/20
15Accepted14ms2688 KiB
16Accepted16ms3400 KiB
17Accepted197ms30516 KiB
18Accepted131ms19252 KiB
19Accepted13ms2868 KiB
20Accepted16ms3396 KiB
21Accepted14ms3424 KiB
22Accepted150ms28204 KiB
23Accepted16ms3312 KiB
24Accepted171ms29108 KiB
subtask420/20
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted64ms12596 KiB
29Accepted67ms11572 KiB
30Accepted48ms10036 KiB
31Accepted54ms11324 KiB
32Accepted43ms9524 KiB
33Accepted64ms12768 KiB
34Accepted67ms13556 KiB
35Accepted48ms9052 KiB
36Accepted59ms12140 KiB
37Accepted61ms12148 KiB
38Accepted114ms23348 KiB
39Accepted291ms55092 KiB
40Accepted307ms55088 KiB
41Accepted289ms55048 KiB
42Accepted270ms55092 KiB
subtask550/50
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted2ms316 KiB
48Accepted2ms316 KiB
49Accepted2ms316 KiB
50Accepted2ms316 KiB
51Accepted1ms316 KiB
52Accepted2ms564 KiB
53Accepted2ms324 KiB
54Accepted14ms2688 KiB
55Accepted16ms3400 KiB
56Accepted197ms30516 KiB
57Accepted131ms19252 KiB
58Accepted13ms2868 KiB
59Accepted16ms3396 KiB
60Accepted14ms3424 KiB
61Accepted150ms28204 KiB
62Accepted16ms3312 KiB
63Accepted171ms29108 KiB
64Accepted64ms12596 KiB
65Accepted67ms11572 KiB
66Accepted48ms10036 KiB
67Accepted54ms11324 KiB
68Accepted43ms9524 KiB
69Accepted64ms12768 KiB
70Accepted67ms13556 KiB
71Accepted48ms9052 KiB
72Accepted59ms12140 KiB
73Accepted61ms12148 KiB
74Accepted114ms23348 KiB
75Accepted291ms55092 KiB
76Accepted307ms55088 KiB
77Accepted289ms55048 KiB
78Accepted270ms55092 KiB
79Accepted72ms12204 KiB
80Accepted70ms13108 KiB
81Accepted56ms9964 KiB
82Accepted50ms9268 KiB
83Accepted63ms11512 KiB
84Accepted90ms13676 KiB
85Accepted56ms10112 KiB
86Accepted46ms8756 KiB
87Accepted71ms13276 KiB
88Accepted83ms13560 KiB
89Accepted63ms9124 KiB
90Accepted76ms13336 KiB
91Accepted85ms14124 KiB
92Accepted71ms12704 KiB
93Accepted79ms12728 KiB
94Accepted92ms13644 KiB
95Accepted74ms13108 KiB
96Accepted71ms13408 KiB
97Accepted72ms13768 KiB
98Accepted50ms9780 KiB
99Accepted241ms39476 KiB
100Accepted317ms45876 KiB
101Accepted79ms12824 KiB
102Accepted238ms42036 KiB
103Accepted354ms40900 KiB
104Accepted349ms59232 KiB
105Accepted314ms57652 KiB
106Accepted388ms59956 KiB
107Accepted349ms57140 KiB