Submission #1120620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120620		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	1550 ms	993604 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int sz=3e7+5;

const int INF=1e18;

const int MOD=1e9+7;

char arr[5000][5000];

vector<int> dx={1,0,-1,0};

vector<int> dy={0,1,0,-1};

int n,m;

bool visited[5000][5000];

bool is_valid(int x,int y,char c)
{
    return (x>=0 && x<n && y>=0 && y<m && !visited[x][y] && arr[x][y]==c);
}

void dfs(int x,int y,char c)
{
    visited[x][y]=true;
    
    for(int i=0;i<4;i++)
        if(is_valid(x+dx[i],y+dy[i],c))
            dfs(x+dx[i],y+dy[i],c);
}

void solve()
{
    cin>>n>>m;
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>arr[i][j];
    
    int cnt=0;
    
    char top=arr[0][0];
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!visited[i][j] && arr[i][j]==top)
            {
                cnt++;
                
                dfs(i,j,top);
            }
        }
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(arr[i][j]!=top && arr[i][j]!='.')
            {
                cout<<cnt+1;
                
                return;
            }
        }
    }
    
    cout<<cnt;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
}

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