Submission #1258037

#TimeUsernameProblemLanguageResultExecution timeMemory
1258037motionTracks in the Snow (BOI13_tracks)C++20
97.81 / 100
1383 ms1114112 KiB
#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int>> q;
int h,w;
vector<vector<char>> grid;
vector<vector<bool>> vis;
void dfs(int x,int y,char z)
{
    if(grid[x][y]==z)
    {
        vis[x][y]=1;
    }
    else
    {
        q.push({x,y});
        return;
    }
    vector<pair<int,int>> g={{1,0},{-1,0},{0,1},{0,-1}};
    for(auto [dx,dy]:g)
    {
        int new_x=x+dx,new_y=dy+y;
        if(new_x<h && new_x>=0 && new_y<w && new_y>=0 && grid[new_x][new_y]!='.' && !vis[new_x][new_y])
        {
            dfs(new_x,new_y,z);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>h>>w;
    grid=vector<vector<char>>(h,vector<char>(w));
    vis=vector<vector<bool>>(h,vector<bool>(w,0));
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>grid[i][j];
        }
    }
    int ans=0;
    char curr='.';
    q.push({0,0});
    while(!q.empty())
    {
        auto [x,y]=q.front();
        q.pop();
        if(vis[x][y]==1) continue;
        if(grid[x][y]!=curr)
        {
            ans++;
            curr=grid[x][y];
        }
        dfs(x,y,curr);
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...