Submission #1177207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177207		t_danh	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	597 ms	110624 KiB

tracks

// https://cses.fi/problemset/task/1653 
/*
 ██████████        ███████                       ██  
░░░░░██░░░        ░██░░░░██                     ░██  
    ░██           ░██    ░██   ██████   ███████ ░██  
    ░██           ░██    ░██  ░░░░░░██ ░░██░░░██░██████
    ░██           ░██    ░██   ███████  ░██  ░██░██░░░██
    ░██           ░██    ██   ██░░░░██  ░██  ░██░██  ░██
    ░██     █████ ░███████   ░░████████ ███  ░██░██  ░██
    ░░     ░░░░░  ░░░░░░░     ░░░░░░░░ ░░░   ░░ ░░   ░░
*/
 
#include <bits/stdc++.h>
#include <deque>
#include <queue>
#define input  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define FOR(i, l, r) for (ll i = l; i <= r; i++)
#define FOR2(i, l, r) for (ll i = l; i >= r; i--)
using namespace std;
using ll = long long;
using str = string;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
 
const ll N = 1e5+1;
const ll LOGN = 19;
const int INF = numeric_limits<int>::max();
const ll MOD = 1e9 + 7;
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
void solve() {
    int n ,m;
    cin >> n >> m;
    vector<vector<char>> matrix(n+1,vector<char>(m+1,'.'));
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            cin >> matrix[i][j];
        }
    }
    function<bool(int,int)> inside = [&](int x , int y){
        return  (x > 0 && x <= n && y > 0 && y <= m && matrix[x][y] != '.');
    };
    vector<vector<int>> depth(n+1,vector<int>(m+1,0));
    deque<pii> q;
    q.pb({1,1});
    depth[1][1] = 1;
    int ans = 0;
    while(!q.empty()){
        pii cur_node = q.front();
        q.pop_front();
        ans = max(ans,depth[cur_node.fi][cur_node.se]);
        for(int i = 0 ; i < 4 ; i++){
            int x = cur_node.fi + dx[i] ,y = cur_node.se + dy[i];
            if(inside(x,y) && depth[x][y] == 0){
                if(matrix[x][y] == matrix[cur_node.fi][cur_node.se]){
                    depth[x][y] = depth[cur_node.fi][cur_node.se];
                    q.push_front({x,y});
                }
                else{
                    depth[x][y] = depth[cur_node.fi][cur_node.se] + 1;
                    q.pb({x,y});
                }

            }
        }
    } 
    cout << ans <<endl;
}

 
int main() {
    input
    const bool cap = true;

    if (cap)
        solve();    
    else {
        ll t;
        cin >> t;
        while (t--) solve();
    }
}

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