Submission #230663

#	Time	Username	Problem	Language	Result	Execution time	Memory
230663		AmineWeslati	Zoo (COCI19_zoo)	C++14	45 / 110	2078 ms	24076 KiB

zoo

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0};

set <pi> s;
int R,C;
char g[1001][1001];
bool vis[1001][1001];
char c;

void dfs(int x, int y){
   s.insert({x,y});
   vis[x][y]=true;
   if(c=='T')g[x][y]='B';
   else g[x][y]='T';

   for(int m=0; m<4; m++){
      int nwx=x+nx[m],nwy=y+ny[m];
      if(nwx<0||nwy<0||nwx>=R||nwy>=C||vis[nwx][nwy]||g[nwx][nwy]!=c) continue;
      dfs(nwx,nwy);
   }
}

int32_t main(){
   boost;
	cin>>R>>C;
	 int nb=0;
	for(int i=0; i<R; i++) for(int j=0; j<C; j++){
      cin>>g[i][j];
      if(g[i][j]!='*') nb++;
	}

	int ans=0;
	while(sz(s)<nb){
      memset(vis,false,sizeof(vis));
      c=g[R-1][C-1];
      dfs(R-1,C-1);
      ans++;
	}
	cout << ans << endl;

   return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 0 / 65