Submission #1327159

#TimeUsernameProblemLanguageResultExecution timeMemory
1327159ninstroyerTracks in the Snow (BOI13_tracks)C++20
100 / 100
668 ms45664 KiB
#include<bits/stdc++.h>
using namespace std;

const int nx = 4e3+5;

int n,m,res=0;
char mat[nx][nx];
queue<pair<int,int>> all, cur;
vector<pair<int,int>> dir = { {1,0}, {-1,0}, {0,1}, {0,-1} };

void bfs(int x, int y)
{
    char base = mat[x][y];
    if(base == '.') return;
    queue<pair<int,int>> q;
    q.push({x,y});
    mat[x][y] = '.';
    while(!q.empty())
    {
        auto [r,c] = q.front();
        q.pop();
        for(auto [rr,cc] : dir)
        {
            int dr = r+rr;
            int dc = c+cc;
            if(mat[dr][dc] == base)
            {
                mat[dr][dc] = '.';
                q.push({dr,dc});
            }
            else if(mat[dr][dc] == (base == 'F' ? 'R' : 'F')) all.push({dr,dc});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin>>mat[i][j];
    all.push({1,1});
    while(!all.empty())
    {
        cur = all;
        if(cur.empty()) break;
        while(!all.empty()) all.pop();
        while(!cur.empty())
        {
            auto [r,c] = cur.front();
            cur.pop();
            bfs(r,c);
        }
        res++;
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...