제출 #1081212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081212		vasu_boda_	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	1207 ms	1048576 KiB

tracks

/*<------------------------------------------------------------------------------------										      	
---------------------------------------------------------------------------------------
----------------------MADE--BY--VB-----------------------------------------------------
---------------------------------------------------------------------------------------
------------------------------------------------------------------------------------>*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// ifstream  i_data("mixmilk.in");
// ofstream  o_data("mixmilk.out");

// #define cin  i_data
// #define cout o_data

/*<--------------------------------DATA--STRUCTURES----------------------------------->*/
#define ll long long
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define si set<int>
#define sc set<char>
#define moj_karvani  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// only less behave as set
//less_equal as multiset
//we can replace less with greater for descending order
/*<--------------------------------FUNCTIONS------------------------------------------->*/
string itob(int num) {if (num == 0) return "0";string binaryString;while (num > 0) {binaryString = (num % 2 == 0 ? "0" : "1") + binaryString;num /= 2;}return binaryString;}
int btoi(const string& binaryString) {return stoi(binaryString, nullptr, 2);}
void print_binary(int num){for(int i=10;i>=0;i--){cout<<((num>>i) & 1);}cout<<endl;}
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool comp(const pair<int, int>& a, const pair<int, int>& b) {if (a.first == b.first) {return a.second < b.second; }return a.first <b.first; };
vector<int> find_intersection(int a,int b,int c,int d,int p,int q,int r ,int s){vector<int>v;int l=max(a,p);int m=max(b,q);int n=min(c,r);int o=min(d,s);int x=n-l;int y=o-m;if(x<0 || y<0){return v;}v.push_back(l);v.push_back(m);v.push_back(n);v.push_back(o);return v;}
/*<-----------------------------BASIC--MATH----------------------------------------->*/
const ll M=1e9+7,N=1e5+5;
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
//ll power(ll a,ll b){if(b==0) return 1;ll res=power(a,b/2);if(b&1){return a*res*res;}else{return res*res;}}
ll power(ll a, ll b){ll ans=1;while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
//ll isPrime(ll a){ if (a != 2 && a % 2 == 0 || a < 2) return 0;  for(ll i = 3; i * i <= a; i += 2) if(a % i == 0) return 0; return 1;}
bool isPrime(int number){if (number <= 1)return false;if (number == 2)return true;if (number % 2 == 0) return false;int boundary = (int)floor(sqrt(number));for (int i = 3; i <= boundary; i += 2)if (number % i == 0)return false;return true;}
/*
SIEVE
int is_prime[1000001];
void seive(){
	int maxN=1000000;
	is_prime[0]=is_prime[1]=0;
	for(int i=2;i<=maxN;i++){
		is_prime[i]=1;
	}
	for(int i=1;i*i<=maxN;i++){
		if(is_prime[i]){
			for(int j=i*i;j<=maxN;j+=i){
				is_prime[j]=0;
			}
		}
	}
}
*/
/*<---------------------------------Solve--here-------------------------------------------->*/

vector<vector<char>>g(4000,vector<char>(4000,'.'));
vector<vector<int>>vis(4000,vector<int>(4000,0));
set<char>s;
void dfs(int i,int j,int m,int n){
    if(i<0 || j<0 || i>=m || j>=n){
        return;
    }
    if(vis[i][j] || g[i][j]=='.')return;
    s.insert(g[i][j]);
    vis[i][j]=1;
    dfs(i-1,j,m,n);
    dfs(i+1,j,m,n);
    dfs(i,j-1,m,n);
    dfs(i,j+1,m,n);
}
void solve(){
	int m,n;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>g[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j] && g[i][j]!='.'){
                s.clear();
                dfs(i,j,m,n);
                ans+=s.size();
            }
        }
    }
    cout<<ans<<endl;
}

/*<-------------------------------Main--Function------------------------------------------>*/
int main(){
	moj_karvani;
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

/*<-------------------------------Thank--You----------------------------------------------->*/

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