Submission #634416

#	Time	Username	Problem	Language	Result	Execution time	Memory
634416		epicci23	Zoo (COCI19_zoo)	C++17	110 / 110	52 ms	4180 KiB

zoo

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define MOD 1000000007
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
const int N=200005;
const long long INF = LLONG_MAX;
const int INF2=(int)1e18;
const int LOG=20;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//sunlari dusun//
/*
 * kodu kisaltcak  fonksiyon
 * cevaba binary search ya da normal bs
 * segment tree / sparse table
 * stack
 * teklik ciftlik
 * precomputation
 * EN ONEMLISI OVERKILLEME
 * edge case dusunr
 * constraintlere bak
 * indisleri kontrol et 
 * dp
 * greedy
 * sorting
 * dfs bfs
 * sieve
*/
bool vis[1001][1001];
char arr[1001][1001];
int n,m,cnt=0;
queue<tuple<int,int,char>> q;
queue<tuple<int,int,char>> q2;
void dfs(int a,int b,char x)
{
	//cout << "a:"  << a << " b: " << b << " x: " << x << endl; 
  if(vis[a][b])
  {
     return;
  }
  vis[a][b]=1;
  if(a+1<=n && !vis[a+1][b] && arr[a+1][b]!='*')
  {
  	if(arr[a+1][b]==x)
  	{
  		dfs(a+1,b,x);
  	}
  	else
  	{
       q2.push({a+1,b,(x=='B' ? 'T' : 'B')});
  	}
  }
  if(a-1>=1 && !vis[a-1][b] && arr[a-1][b]!='*')
  {
  	if(arr[a-1][b]==x)
  	{
  		dfs(a-1,b,x);
  	}
  	else
  	{
       q2.push({a-1,b,(x=='B' ? 'T' : 'B')});
  	}
  }
  if(b+1<=m && !vis[a][b+1] && arr[a][b+1]!='*')
  {
  	if(arr[a][b+1]==x)
  	{
  		dfs(a,b+1,x);
  	}
  	else
  	{
       q2.push({a,b+1,(x=='B' ? 'T' : 'B')});
  	}
  }
  if(b-1>=1 && !vis[a][b-1] && arr[a][b-1]!='*')
  {
  	if(arr[a][b-1]==x)
  	{
  		dfs(a,b-1,x);
  	}
  	else
  	{
       q2.push({a,b-1,(x=='B' ? 'T' : 'B')});
  	}
  }
}

void solve()
{
	cin >> n >> m;
	
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> arr[i][j];
    q2.push({1,1,(arr[1][1]=='B' ? 'B' : 'T')});
    while(!q2.empty())
    {
      cnt++;
      while(!q2.empty())
      {
      	q.push(q2.front());
      	//cout << get<0>(q2.front()) << " " << get<1>(q2.front()) << endl;
      	q2.pop();
      }
      while(!q.empty())
      {
        tuple<int,int,char> cur=q.front();
        q.pop();
       // cout << "a" << "\n";
        dfs(get<0>(cur),get<1>(cur),get<2>(cur));
      }
    }
    cout << cnt << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
 int t=1;//cin>> t;
 
 while(t--) solve();
 
 return 0;
}

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