Submission #1214747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214747		behesht	Tracks in the Snow (BOI13_tracks)	C++20	97.81 / 100	949 ms	1114112 KiB

tracks

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define ld                   long double
#define ll                   long long
#define pb                   push_back
#define arr(x)               array <int, x>
#define endl                 '\n'
// #define int                  long long

using namespace std;

const int INF = 1e9 + 24 + (33 / 10); // 33 ---> 34
const int MAXN = 4e3 + 24 + (33 / 10); // 33 ---> 34

int dx[4] = {1, -1, -0, -0};
int dy[4] = {-0, -0, 1, -1};

int n, m;
vector <int> v;
bool vis[MAXN][MAXN];
bool a[MAXN][MAXN];
int ans = 0;

void dfs(int x, int y){

    vis[x][y] = 1;
    v.pb((x - 1) * m + (y - 1));

    for(int i = 0; i < 4; i++){

        int nx = x + dx[i];
        int ny = y + dy[i];

        if(a[nx][ny] == a[x][y] && !vis[nx][ny])
            dfs(nx, ny);
    }
}

void solve(vector <int> vec){

    if(vec.empty())
        return;
    
    v.clear();
    ans++;

    for(auto eli : vec){

        int x = eli / m + 1;
        int y = eli % m + 1;

        for(int i = 0; i < 4; i++){

            int nx = x + dx[i];
            int ny = y + dy[i];

            if(!vis[nx][ny])
                dfs(nx, ny);
        }
    }

    solve(v);
}

signed main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char eli;
            cin >> eli;
            
            if(eli == 'F')
                a[i][j] = 1;
            
            else if(eli == 'R')
                a[i][j] = 0;
            
            else 
                vis[i][j] = 1;
        }
    }

    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= m + 1; j++)
            if(!i || !j || i == n + 1 || j == m + 1)
                vis[i][j] = 1;

    
    dfs(1, 1);
    solve(v);

    cout << ans << endl;
}

// Man hamooonam ke ye rooz...

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