답안 #1101660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101660	2024-10-16T14:35:05 Z	vanea	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	679 ms	177732 KB

tracks

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

const int mxN = 4e3+10;

vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

bool vis[mxN][mxN];
int h, w;

bool valid(int a, int b) {
    return (a >= 0 && a < h && b >= 0 && b < w && !vis[a][b]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> h >> w;
    int ans = 0;
    vector<string> v(h);
    for(int i = 0; i < h; i++) {
        cin >> v[i];
    }
    deque<array<int, 3>> q;
    q.push_back({1, 0, 0});
    while(!q.empty()) {
        int curr = q.front()[0], x = q.front()[1], y = q.front()[2];
        ans = max(ans, curr);
        vis[x][y] = true;
        q.pop_front();
        for(int k = 0; k < 4; k++) {
            int a = x+xy[k], b = y+yx[k];
            if(valid(a, b) && v[a][b] != '.') {
                if(v[a][b] == v[x][y]) q.push_front({curr, a, b});
                else q.push_back({curr+1, a, b});
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	2896 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	8 ms	3244 KB	Output is correct
5	Correct	3 ms	1616 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	592 KB	Output is correct
8	Correct	2 ms	592 KB	Output is correct
9	Correct	2 ms	848 KB	Output is correct
10	Correct	3 ms	1360 KB	Output is correct
11	Correct	3 ms	1292 KB	Output is correct
12	Correct	6 ms	1616 KB	Output is correct
13	Correct	4 ms	1616 KB	Output is correct
14	Correct	2 ms	1628 KB	Output is correct
15	Correct	13 ms	2640 KB	Output is correct
16	Correct	16 ms	2908 KB	Output is correct
17	Correct	9 ms	2640 KB	Output is correct
18	Correct	7 ms	3068 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	15440 KB	Output is correct
2	Correct	40 ms	7088 KB	Output is correct
3	Correct	168 ms	33968 KB	Output is correct
4	Correct	43 ms	11856 KB	Output is correct
5	Correct	116 ms	21840 KB	Output is correct
6	Correct	669 ms	81040 KB	Output is correct
7	Correct	11 ms	16208 KB	Output is correct
8	Correct	10 ms	15456 KB	Output is correct
9	Correct	2 ms	592 KB	Output is correct
10	Correct	1 ms	508 KB	Output is correct
11	Correct	10 ms	15952 KB	Output is correct
12	Correct	1 ms	1016 KB	Output is correct
13	Correct	38 ms	7104 KB	Output is correct
14	Correct	22 ms	5068 KB	Output is correct
15	Correct	10 ms	5456 KB	Output is correct
16	Correct	20 ms	2792 KB	Output is correct
17	Correct	94 ms	12776 KB	Output is correct
18	Correct	40 ms	12372 KB	Output is correct
19	Correct	39 ms	11856 KB	Output is correct
20	Correct	42 ms	10832 KB	Output is correct
21	Correct	104 ms	22608 KB	Output is correct
22	Correct	108 ms	22056 KB	Output is correct
23	Correct	192 ms	18940 KB	Output is correct
24	Correct	85 ms	22400 KB	Output is correct
25	Correct	212 ms	33864 KB	Output is correct
26	Correct	431 ms	177732 KB	Output is correct
27	Correct	511 ms	113632 KB	Output is correct
28	Correct	679 ms	81048 KB	Output is correct
29	Correct	660 ms	78800 KB	Output is correct
30	Correct	606 ms	98060 KB	Output is correct
31	Correct	608 ms	25928 KB	Output is correct
32	Correct	462 ms	104664 KB	Output is correct