Submission #1242748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242748		atharv_s_13	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	948 ms	294884 KiB

tracks

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<string>grid(4002);
int ans=0;


void floodfill(int r,int c,vector<vector<bool>>&visited,char &k)
{
    stack<pair<int,int>>q;
    q.push({r,c});
    bool mark=false;
    while(!q.empty())
    {
        r=q.top().first,c=q.top().second;
        q.pop();

        if(r<0 || c<0 || r>=n || c>=m || grid[r][c]=='.') continue;
        if(visited[r][c]) continue;
        visited[r][c]=true;

        if(k!=grid[r][c] && !mark)
        {
            ans++;
            mark=true;
        }

        q.push({r-1,c});
        q.push({r,c-1});
        q.push({r+1,c});
        q.push({r,c+1});
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 0;i<n; i++)
    {
        cin>>grid[i];
    }
    vector<vector<bool>>visited(n,vector<bool>(m,false));

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!visited[i][j] && grid[i][j]!='.')
            {
                ans++;
                floodfill(i,j,visited,grid[i][j]);
            }
        }
    }
    cout<<ans;
    



    return 0;
}

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