답안 #990788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990788 2024-05-31T10:55:58 Z kfhjad Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
695 ms 1048576 KB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int H, W;
string meadow[4000];
int val[4000][4000];
queue<pair<int, int>> q;

int switches;
char animal;
bool cnt;

void dfs(int row, int col)
{
    if (row < 0 || col < 0 || row == H || col == W || meadow[row][col] == '.')
        return;
    
    if (val[row][col] != 0 && cnt)
        return;

    cnt = true;

    if (animal != meadow[row][col])
    {
        q.push({row, col});
        val[row][col] = switches + 1;
        return;
    }

    val[row][col] = switches;

    dfs(row + 1, col);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row, col - 1);
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    cin >> H >> W;

    for (auto& i : meadow)
        cin >> i;
    
    q.push({0, 0});
    val[0][0] = 1;

    while (!q.empty())
    {
        auto [row, col] = q.front();
        q.pop();

        switches = val[row][col];
        animal = meadow[row][col];
        cnt = false;
        dfs(row, col);
    }
    
    int ans = 0;

    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
            ans = max(ans, val[i][j]);

    cout << ans << endl;

    return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3676 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 2 ms 1988 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 4 ms 2136 KB Output is correct
13 Correct 2 ms 2140 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 7 ms 3676 KB Output is correct
16 Correct 9 ms 3672 KB Output is correct
17 Correct 6 ms 3676 KB Output is correct
18 Correct 6 ms 4444 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16220 KB Output is correct
2 Correct 27 ms 10576 KB Output is correct
3 Correct 147 ms 60500 KB Output is correct
4 Correct 47 ms 26196 KB Output is correct
5 Correct 143 ms 43408 KB Output is correct
6 Correct 536 ms 138816 KB Output is correct
7 Correct 8 ms 16984 KB Output is correct
8 Correct 8 ms 16216 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 7 ms 16572 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct
13 Correct 27 ms 10588 KB Output is correct
14 Correct 15 ms 7260 KB Output is correct
15 Correct 12 ms 9480 KB Output is correct
16 Correct 13 ms 4696 KB Output is correct
17 Correct 73 ms 21744 KB Output is correct
18 Correct 53 ms 28496 KB Output is correct
19 Correct 46 ms 26192 KB Output is correct
20 Correct 38 ms 19384 KB Output is correct
21 Correct 96 ms 42068 KB Output is correct
22 Correct 136 ms 43400 KB Output is correct
23 Correct 145 ms 35408 KB Output is correct
24 Correct 100 ms 38992 KB Output is correct
25 Correct 223 ms 81488 KB Output is correct
26 Runtime error 648 ms 1048576 KB Execution killed with signal 9
27 Correct 687 ms 383556 KB Output is correct
28 Correct 523 ms 138764 KB Output is correct
29 Correct 505 ms 129440 KB Output is correct
30 Correct 559 ms 188388 KB Output is correct
31 Correct 356 ms 62920 KB Output is correct
32 Correct 695 ms 409428 KB Output is correct