제출 #1120842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120842		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	1848 ms	1048576 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);
            }
        }
    }
    
    int comp=0;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(arr[i][j]==top && arr[i][j]=='F')
                arr[i][j]='R';
            
            else if(arr[i][j]==top && arr[i][j]=='R')
                arr[i][j]='F';
            
            visited[i][j]=false;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!visited[i][j] &&  arr[i][j]!='.')
            {
                comp++;
                
                dfs(i,j,arr[i][j]);
            }
        }
    }
    
    cout<<cnt+comp;
}

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: 0 / 70