oj.uz

답안 #444368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444368 2021-07-13T19:11:14 Z mhsi2005 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1491 ms 127116 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 4000 + 10, INF = 1e9 + 10;

int n, m, h, w, d[maxn][maxn], mx;
bool vis[maxn];
char meadow[maxn][maxn];

int main() {
    memset(d, INF, sizeof(d));
    cin >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> meadow[i][j];
    int adjx[4]{1, -1, 0, 0}, adjy[4]{0, 0, 1, -1};
    d[1][1] = 0;
    deque<pair<int, int>> q;
    q.push_back({1, 1});
    while (q.size()) {
        auto v = q.front();
        q.pop_front();
        for (int i = 0; i < 4; i++) {
            int x = v.first + adjx[i],
                y = v.second + adjy[i];
            if (x < 1 || y < 1 || x > h || y > w || meadow[x][y] == '.') continue;
            int w = !(meadow[v.first][v.second] == meadow[x][y]);
            if (d[v.first][v.second] + w < d[x][y]) {
                d[x][y] = d[v.first][v.second] + w;
                mx = max(mx, d[x][y]);
                if (w == 1)
                    q.push_back({x, y});
                else
                    q.push_front({x, y});
            }
        }
    }
    cout << mx + 1 << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 65220 KB Output is correct
2 Correct 26 ms 63276 KB Output is correct
3 Correct 27 ms 63324 KB Output is correct
4 Correct 42 ms 65276 KB Output is correct
5 Correct 33 ms 64320 KB Output is correct
6 Correct 27 ms 63256 KB Output is correct
7 Correct 27 ms 63436 KB Output is correct
8 Correct 28 ms 63400 KB Output is correct
9 Correct 28 ms 63564 KB Output is correct
10 Correct 31 ms 64172 KB Output is correct
11 Correct 32 ms 63940 KB Output is correct
12 Correct 37 ms 64316 KB Output is correct
13 Correct 33 ms 64288 KB Output is correct
14 Correct 33 ms 64356 KB Output is correct
15 Correct 50 ms 65148 KB Output is correct
16 Correct 51 ms 65100 KB Output is correct
17 Correct 47 ms 65120 KB Output is correct
18 Correct 42 ms 65296 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 78144 KB Output is correct
2 Correct 149 ms 68140 KB Output is correct
3 Correct 1089 ms 79004 KB Output is correct
4 Correct 291 ms 70596 KB Output is correct
5 Correct 671 ms 75064 KB Output is correct
6 Correct 1474 ms 92572 KB Output is correct
7 Correct 37 ms 78796 KB Output is correct
8 Correct 35 ms 78196 KB Output is correct
9 Correct 31 ms 63196 KB Output is correct
10 Correct 30 ms 63256 KB Output is correct
11 Correct 37 ms 78596 KB Output is correct
12 Correct 29 ms 63820 KB Output is correct
13 Correct 147 ms 68124 KB Output is correct
14 Correct 96 ms 66804 KB Output is correct
15 Correct 100 ms 67012 KB Output is correct
16 Correct 78 ms 64716 KB Output is correct
17 Correct 342 ms 71108 KB Output is correct
18 Correct 320 ms 71056 KB Output is correct
19 Correct 288 ms 70644 KB Output is correct
20 Correct 262 ms 70316 KB Output is correct
21 Correct 648 ms 75332 KB Output is correct
22 Correct 672 ms 75016 KB Output is correct
23 Correct 631 ms 73024 KB Output is correct
24 Correct 641 ms 75332 KB Output is correct
25 Correct 1298 ms 79048 KB Output is correct
26 Correct 1041 ms 127116 KB Output is correct
27 Correct 1372 ms 105728 KB Output is correct
28 Correct 1491 ms 92760 KB Output is correct
29 Correct 1472 ms 90860 KB Output is correct
30 Correct 1417 ms 96632 KB Output is correct
31 Correct 1028 ms 76328 KB Output is correct
32 Correct 1309 ms 94220 KB Output is correct