oj.uz

답안 #757472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757472 2023-06-13T08:27:46 Z The_Samurai Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1630 ms 245684 KB 
#include "bits/stdc++.h"

using namespace std;

int INF = 1e9;
vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    clock_t startTime = clock();

    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m, '.'));
    int cnt_not = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] != '.') {
                cnt_not++;
            }
        }
    }
    if (max(n, m) == 1) {
        cout << 1;
        return 0;
    }
    vector<pair<int, int>> can = {{0, 0}};
    vector<vector<bool>> vis(n, vector<bool>(m));
    char x = a[0][0];
    vis[0][0] = true;
    cnt_not--;
    int ans = 0;
    while (cnt_not > 0) {
        ans++;
        vector<pair<int, int>> nw_can = {{0, 0}};
        for (int p = 0; p < can.size(); p++) {
            auto [i, j] = can[p];
            for (int k = 0; k < 4; k++) {
                int ii = i + dx[k];
                int jj = j + dy[k];
                if (min(ii, jj) < 0 or ii == n or jj == m) continue;
                if (vis[ii][jj]) continue;
                if (a[ii][jj] == x) {
                    nw_can.emplace_back(ii, jj);
                    can.emplace_back(ii, jj);
                    vis[ii][jj] = true;
                    cnt_not--;
                }
            }
        }
        x = (x == 'R' ? 'F' : 'R');
        can = nw_can;
    }
    cout << ans;



#ifdef sunnitov
    cerr << "\nTime: " << (int)((double)(clock() - startTime) / CLOCKS_PER_SEC * 1000);
#endif
}

/*
 5 6
 FFFFFF
 RRRRRF
 F...RF
 F...RF
 F..RRF
 FFFRRF
*/

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int p = 0; p < can.size(); p++) {
      |                         ~~^~~~~~~~~~~~
tracks.cpp:11:13: warning: unused variable 'startTime' [-Wunused-variable]
   11 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1156 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 14 ms 2900 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 1124 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 19 ms 852 KB Output is correct
16 Correct 23 ms 1156 KB Output is correct
17 Correct 16 ms 724 KB Output is correct
18 Correct 13 ms 3000 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 90 ms 2400 KB Output is correct
3 Correct 557 ms 18548 KB Output is correct
4 Correct 117 ms 4784 KB Output is correct
5 Correct 523 ms 10612 KB Output is correct
6 Correct 1630 ms 193096 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 84 ms 2348 KB Output is correct
14 Correct 68 ms 1492 KB Output is correct
15 Correct 38 ms 1452 KB Output is correct
16 Correct 39 ms 1236 KB Output is correct
17 Correct 217 ms 5212 KB Output is correct
18 Correct 164 ms 5080 KB Output is correct
19 Correct 116 ms 4784 KB Output is correct
20 Correct 126 ms 4304 KB Output is correct
21 Correct 326 ms 11032 KB Output is correct
22 Correct 513 ms 10608 KB Output is correct
23 Correct 445 ms 9452 KB Output is correct
24 Correct 337 ms 10720 KB Output is correct
25 Correct 665 ms 18412 KB Output is correct
26 Correct 710 ms 211188 KB Output is correct
27 Correct 1288 ms 215436 KB Output is correct
28 Correct 1621 ms 193032 KB Output is correct
29 Correct 1609 ms 189040 KB Output is correct
30 Correct 1353 ms 245684 KB Output is correct
31 Correct 1097 ms 15236 KB Output is correct
32 Correct 1193 ms 216560 KB Output is correct