Submission #990788

#	Time	Username	Problem	Language	Result	Execution time	Memory
990788		kfhjad	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	695 ms	1048576 KiB

tracks

#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
 */

• Subtask 1: 30 / 30
• Subtask 2: 67.8125 / 70