Submission #1120457

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

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<char>> grid(4500,vector<char>(4500));
vector<vector<bool>> vis(4500,vector<bool>(4500,0));
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
int n,m;
int cnt=0;
void dfs(int i,int j,int qat,vector<pair<int,int>> &yolla){
    vis[i][j] = 1;
    for(int ind =0;ind < 4;++ind){
        int x = i + dx[ind];
        int y = j + dy[ind];
        if(x > n || x == 0 || y > m || y == 0){
            continue;
        }
        if(grid[x][y] == '.')continue;
        if(vis[x][y])continue;
        if(grid[x][y] != grid[i][j]){
            yolla.push_back({x,y});
        }else dfs(x,y,qat,yolla);
    }
}
signed main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin >> grid[i][j];
        }
    }
    vector<pair<int,int>> nextt,nextt2,emptyy;
    dfs(1,1,1,nextt);
    // for(int i=1;i<=n;++i){
    //     for(int j=1;j<=m;++j)cout << vis[i][j] << ' ';
    //     cout << '\n';
    // }
    int curr=1;
    while(!nextt.empty()){
        // cout << "GIRDI";
        curr++;
        nextt2.clear();
        while(!nextt.empty()){
            auto &[x,y] = nextt.back();
            nextt.pop_back();
            dfs(x,y,curr,nextt2);
        }
        nextt = nextt2;
    }
    cout << curr;

    
}
// FFRF....
// .FRRR...
// .FFFFF..
// ..RRRFFR
// .....FFF

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