Submission #873332

#	Time	Username	Problem	Language	Result	Execution time	Memory
873332		jhon06	Tracks in the Snow (BOI13_tracks)	C++14	5 / 100	2146 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define maxl LLONG_MAX
#define minl LLONG_MIN
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define nd end()
#define rnd(x) random_shuffle((x).begin, (x).end())
#define reverse(x) reverse((x).begin(), (x).end())
#define del erase
#define ssub substr
#define tp tuple
#define pp pop_back
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<ll>
#define vii vector<pair<ll,ll>>
#define LSOne(x) (x&(-x))
#define log2(i) (__builtin_clzll(1) - __builtin_clzll(i))
#define gdc(a,b) __gcd(a,b)
#define lcm(a,b) ((a*b)/gdc(a,b))
#define dbg(x) (cerr<<"["<<"R"<<":"<<__LINE__<<"]"<<#x<<" -> "<<(x)<<'\n',(x))
#define rand (rand() * (RAND_MAX + 1) + rand()) % (int)1e6
#define count(x) __builtin_popcount(x)
//lower_bound(arr,arr+a,valore); unique() remove dups fill(vec,number) merge() binary_search()
//601 div2 b
using namespace std;
int n,m;
char mat[4000][4000];
bool vis[4000][4000];
bool valido(int i,int j){
	if(i<0 || j<0 || i>=n || j>=m)return 0;
	return 1;
}
void dfs(char (&mat)[4000][4000],int i,int j){
	int c[]={1,-1,0,0};
	int r[]={0,0,1,-1};
	vis[i][j]=true;
	for(int a=0;a<4;a++){
		for(int b=0;b<4;b++){
			if(valido(i+r[a],j+c[b])){
				if(mat[i+r[a]][j+c[b]]==mat[i][j] || mat[i+r[a]][j+c[b]]==1 || mat[i][j]==1){
					if(vis[i+r[a]][j+c[b]])continue;
					dfs(mat,i+r[a],j+c[b]);
				}
			}
		}
	}
	mat[i][j]=1;
}
void compute(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mat[i][j];
		//	cout<<mat[i][j]<<" ";
		}
	//	cout<<'\n';
	}
	int conta=1;
	dfs(mat,n-1,m-1);
/*	dfs(mat,0,2);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<mat[i][j]<<" ";
		}
		cout<<'\n';
	}*/
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(mat[i][j]!=1 && mat[i][j]!='.'){
			//	cout<<i<<" "<<j<<'\n';
				memset(vis,0,sizeof(vis));
				dfs(mat,i,j);
				conta++;
			}
			
		}
	}
	cout<<conta;
}
int main(int argc, char** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);
 // freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int t;
    t=1;
  //  cin>>t;
    for(int i=1;i<=t;i++){
      //cout<<"Case #"<<i<<": "<<compute()<<'\n';
        compute();
    }
    return 0;
}

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