Submission #19,185

19185

2025-11-28 14:38:45

cpp17

Accepted 100/100

465ms

42492 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;
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
			1	Accepted	1ms	316 KiB
			2	Accepted	1ms	500 KiB
			3	Accepted	1ms	316 KiB
	subtask2	10/10
			4	Accepted	1ms	316 KiB
			5	Accepted	1ms	316 KiB
			6	Accepted	1ms	508 KiB
			7	Accepted	3ms	1100 KiB
			8	Accepted	3ms	1220 KiB
			9	Accepted	3ms	1016 KiB
			10	Accepted	3ms	1076 KiB
			11	Accepted	2ms	1076 KiB
			12	Accepted	2ms	820 KiB
			13	Accepted	3ms	1076 KiB
			14	Accepted	3ms	1332 KiB
	subtask3	20/20
			15	Accepted	28ms	10772 KiB
			16	Accepted	29ms	12844 KiB
			17	Accepted	256ms	34428 KiB
			18	Accepted	175ms	27192 KiB
			19	Accepted	27ms	11064 KiB
			20	Accepted	34ms	12764 KiB
			21	Accepted	21ms	2356 KiB
			22	Accepted	215ms	16696 KiB
			23	Accepted	21ms	2100 KiB
			24	Accepted	221ms	17972 KiB
	subtask4	20/20
			25	Accepted	1ms	316 KiB
			26	Accepted	1ms	316 KiB
			27	Accepted	1ms	508 KiB
			28	Accepted	97ms	13108 KiB
			29	Accepted	90ms	12864 KiB
			30	Accepted	79ms	11572 KiB
			31	Accepted	90ms	16324 KiB
			32	Accepted	71ms	11664 KiB
			33	Accepted	100ms	14644 KiB
			34	Accepted	101ms	15444 KiB
			35	Accepted	71ms	12556 KiB
			36	Accepted	98ms	16692 KiB
			37	Accepted	96ms	16692 KiB
			38	Accepted	184ms	14384 KiB
			39	Accepted	381ms	24116 KiB
			40	Accepted	404ms	24116 KiB
			41	Accepted	386ms	23952 KiB
			42	Accepted	407ms	24116 KiB
	subtask5	50/50
			43	Accepted	1ms	316 KiB
			44	Accepted	1ms	316 KiB
			45	Accepted	1ms	508 KiB
			46	Accepted	3ms	1100 KiB
			47	Accepted	3ms	1220 KiB
			48	Accepted	3ms	1016 KiB
			49	Accepted	3ms	1076 KiB
			50	Accepted	2ms	1076 KiB
			51	Accepted	2ms	820 KiB
			52	Accepted	3ms	1076 KiB
			53	Accepted	3ms	1332 KiB
			54	Accepted	28ms	10772 KiB
			55	Accepted	29ms	12844 KiB
			56	Accepted	256ms	34428 KiB
			57	Accepted	175ms	27192 KiB
			58	Accepted	27ms	11064 KiB
			59	Accepted	34ms	12764 KiB
			60	Accepted	21ms	2356 KiB
			61	Accepted	215ms	16696 KiB
			62	Accepted	21ms	2100 KiB
			63	Accepted	221ms	17972 KiB
			64	Accepted	97ms	13108 KiB
			65	Accepted	90ms	12864 KiB
			66	Accepted	79ms	11572 KiB
			67	Accepted	90ms	16324 KiB
			68	Accepted	71ms	11664 KiB
			69	Accepted	100ms	14644 KiB
			70	Accepted	101ms	15444 KiB
			71	Accepted	71ms	12556 KiB
			72	Accepted	98ms	16692 KiB
			73	Accepted	96ms	16692 KiB
			74	Accepted	184ms	14384 KiB
			75	Accepted	381ms	24116 KiB
			76	Accepted	404ms	24116 KiB
			77	Accepted	386ms	23952 KiB
			78	Accepted	407ms	24116 KiB
			79	Accepted	115ms	23348 KiB
			80	Accepted	112ms	20020 KiB
			81	Accepted	85ms	18484 KiB
			82	Accepted	79ms	16436 KiB
			83	Accepted	97ms	19252 KiB
			84	Accepted	119ms	27956 KiB
			85	Accepted	86ms	16180 KiB
			86	Accepted	78ms	17184 KiB
			87	Accepted	112ms	18740 KiB
			88	Accepted	114ms	21552 KiB
			89	Accepted	81ms	16788 KiB
			90	Accepted	108ms	18520 KiB
			91	Accepted	115ms	19764 KiB
			92	Accepted	109ms	16188 KiB
			93	Accepted	108ms	19120 KiB
			94	Accepted	112ms	19612 KiB
			95	Accepted	115ms	20788 KiB
			96	Accepted	111ms	14132 KiB
			97	Accepted	108ms	19252 KiB
			98	Accepted	78ms	15016 KiB
			99	Accepted	319ms	29748 KiB
			100	Accepted	395ms	42492 KiB
			101	Accepted	109ms	18996 KiB
			102	Accepted	321ms	34624 KiB
			103	Accepted	365ms	40132 KiB
			104	Accepted	456ms	37172 KiB
			105	Accepted	426ms	34100 KiB
106	Accepted		465ms	40172 KiB
107	Accepted		441ms	33336 KiB