답안 #842602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842602	2023-09-03T05:33:07 Z	Qang	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	423 ms	118852 KB

tracks

#include <bits/stdc++.h> // 0/1 BFS
using namespace std;
#define MAXN 4001
string g[MAXN];
int n, m, depth[MAXN][MAXN], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; 

bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && g[i][j] != '.';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> g[i];
    depth[0][0] = 1; //depth[i][j] = 0 means unvisited
    deque<pair<int, int>> q;
    q.push_back({ 0, 0 });
    int ans = 1;
    while (!q.empty()) {
        auto z = q.front();
        q.pop_front();
        ans = max(ans, depth[z.first][z.second]);
        for (int i = 0; i < 4; ++i) {
            int f = z.first + dx[i], s = z.second + dy[i];
            if (inside(f, s) && depth[f][s] == 0) {
                if (g[f][s] == g[z.first][z.second]) {
                    depth[f][s] = depth[z.first][z.second];
                    q.push_front({ f, s });
                }
                else {
                    depth[f][s] = depth[z.first][z.second] + 1;
                    q.push_back({ f, s });
                }
            }
        }
    }
    cout << ans;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	3672 KB	Output is correct
2	Correct	0 ms	632 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	5 ms	3416 KB	Output is correct
5	Correct	2 ms	1880 KB	Output is correct
6	Correct	0 ms	600 KB	Output is correct
7	Correct	0 ms	600 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	2 ms	1624 KB	Output is correct
11	Correct	2 ms	1624 KB	Output is correct
12	Correct	3 ms	2136 KB	Output is correct
13	Correct	2 ms	1884 KB	Output is correct
14	Correct	2 ms	1880 KB	Output is correct
15	Correct	7 ms	3416 KB	Output is correct
16	Correct	8 ms	3672 KB	Output is correct
17	Correct	6 ms	3416 KB	Output is correct
18	Correct	4 ms	3420 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15960 KB	Output is correct
2	Correct	25 ms	10320 KB	Output is correct
3	Correct	136 ms	59788 KB	Output is correct
4	Correct	41 ms	25680 KB	Output is correct
5	Correct	107 ms	42764 KB	Output is correct
6	Correct	416 ms	95420 KB	Output is correct
7	Correct	7 ms	16728 KB	Output is correct
8	Correct	7 ms	15964 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	7 ms	16472 KB	Output is correct
12	Correct	1 ms	1112 KB	Output is correct
13	Correct	25 ms	10588 KB	Output is correct
14	Correct	15 ms	7000 KB	Output is correct
15	Correct	12 ms	9304 KB	Output is correct
16	Correct	13 ms	4440 KB	Output is correct
17	Correct	67 ms	21328 KB	Output is correct
18	Correct	49 ms	28240 KB	Output is correct
19	Correct	41 ms	25680 KB	Output is correct
20	Correct	34 ms	19024 KB	Output is correct
21	Correct	86 ms	41532 KB	Output is correct
22	Correct	112 ms	42732 KB	Output is correct
23	Correct	130 ms	34964 KB	Output is correct
24	Correct	85 ms	38992 KB	Output is correct
25	Correct	306 ms	81040 KB	Output is correct
26	Correct	214 ms	118852 KB	Output is correct
27	Correct	303 ms	110188 KB	Output is correct
28	Correct	423 ms	95400 KB	Output is correct
29	Correct	403 ms	91512 KB	Output is correct
30	Correct	363 ms	99088 KB	Output is correct
31	Correct	320 ms	62100 KB	Output is correct
32	Correct	288 ms	100328 KB	Output is correct