답안 #332238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332238	2020-12-01T18:30:12 Z	dolphingarlic	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	717 ms	130812 KB

tracks

#include <bits/stdc++.h>
using namespace std;

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

int n, m, depth[4000][4000], ans = 1;
string snow[4000];

bool inside(int x, int y) {
    return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> snow[i];

    deque<pair<int, int>> q;
    q.push_back({0, 0});
    depth[0][0] = 1;

    while (q.size()) {
        pair<int, int> c = q.front();
        q.pop_front();
        ans = max(ans, depth[c.first][c.second]);

        for (int i = 0; i < 4; i++) {
            int x = c.first + dx[i], y = c.second + dy[i];
            if (inside(x, y) && depth[x][y] == 0) {
                if (snow[x][y] == snow[c.first][c.second]) {
                    depth[x][y] = depth[c.first][c.second];
                    q.push_front({x, y});
                } else {
                    depth[x][y] = depth[c.first][c.second] + 1;
                    q.push_back({x, y});
                }
            }
        }
    }

    cout << ans;
    return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	3948 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	9 ms	3564 KB	Output is correct
5	Correct	4 ms	2028 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	748 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	3 ms	1772 KB	Output is correct
11	Correct	3 ms	1516 KB	Output is correct
12	Correct	6 ms	2156 KB	Output is correct
13	Correct	4 ms	2028 KB	Output is correct
14	Correct	3 ms	2028 KB	Output is correct
15	Correct	12 ms	3692 KB	Output is correct
16	Correct	15 ms	3948 KB	Output is correct
17	Correct	11 ms	3692 KB	Output is correct
18	Correct	9 ms	3564 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	15852 KB	Output is correct
2	Correct	44 ms	12012 KB	Output is correct
3	Correct	224 ms	75500 KB	Output is correct
4	Correct	74 ms	29420 KB	Output is correct
5	Correct	191 ms	51308 KB	Output is correct
6	Correct	709 ms	110088 KB	Output is correct
7	Correct	12 ms	16620 KB	Output is correct
8	Correct	14 ms	15892 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	1 ms	620 KB	Output is correct
11	Correct	16 ms	16364 KB	Output is correct
12	Correct	2 ms	1260 KB	Output is correct
13	Correct	55 ms	12012 KB	Output is correct
14	Correct	30 ms	7916 KB	Output is correct
15	Correct	22 ms	10348 KB	Output is correct
16	Correct	21 ms	4972 KB	Output is correct
17	Correct	117 ms	25324 KB	Output is correct
18	Correct	87 ms	32180 KB	Output is correct
19	Correct	75 ms	29420 KB	Output is correct
20	Correct	58 ms	22508 KB	Output is correct
21	Correct	158 ms	50688 KB	Output is correct
22	Correct	203 ms	51436 KB	Output is correct
23	Correct	241 ms	42408 KB	Output is correct
24	Correct	139 ms	47632 KB	Output is correct
25	Correct	460 ms	96492 KB	Output is correct
26	Correct	436 ms	130812 KB	Output is correct
27	Correct	581 ms	123292 KB	Output is correct
28	Correct	717 ms	110084 KB	Output is correct
29	Correct	702 ms	108512 KB	Output is correct
30	Correct	658 ms	112368 KB	Output is correct
31	Correct	708 ms	72172 KB	Output is correct
32	Correct	503 ms	108328 KB	Output is correct