Submission #1155631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155631		sabino1	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	447 ms	88452 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define lef(x) (x<<1)
#define rig(x) (lef(x)|1)
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
const int MAX = 4e3+10;
const ll mod = 998244353;
const int inf = 1e9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct info{
    int x,y;
    char c;

    info(int x,int y, char c) : x(x), y(y), c(c){}
};

char a[MAX][MAX];
vector<pair<int,int>> movs = {{1,0},{-1,0},{0,1},{0,-1}};

int solve(int n,int m){
    int ans = 1;
    deque<info> q;
    char at = a[n-1][m-1];
    a[n-1][m-1] = '.';
    q.push_front(info(n-1,m-1,at));
    while(!q.empty()){
        auto [x,y,c] = q.front();
        if(at != c) {
            ans++;
            at = c;
        }
        q.pop_front();
        for(auto v : movs){
            int x2,y2;
            x2 = x + v.first;
            y2 = y + v.second;
            if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || a[x2][y2] == '.') continue;
            if(a[x2][y2] == at) q.push_front(info(x2,y2,a[x2][y2]));
            else q.push_back(info(x2,y2,a[x2][y2]));
            a[x2][y2] = '.';
        }
    }
    return ans;
}

void test() {
    int n,m;
    cin >> n >> m;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> a[i][j];
    cout << solve(n,m) << '\n';
}
 
int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t=1;
    // cin >> t;    
    while(t--) test();
    return 0;
}

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