Submission #337606

#	Time	Username	Problem	Language	Result	Execution time	Memory
337606		mosiashvililuka	Zoo (COCI19_zoo)	C++14	110 / 110	184 ms	45856 KiB

zoo

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009][1009],cnt,bo[1009][1009],dis[1000009];
string s;
vector <int> v[1000009];
deque <int> de;
void check(int q, int w, int rr);
void dfs(int q, int w);
void check(int q, int w, int rr){
	if(q<1||q>a||w<1||w>b) return;
	if(bo[q][w]!=0||f[q][w]!=rr) return;
	dfs(q,w);
}
void dfs(int q, int w){
	bo[q][w]=cnt;
	check(q-1,w,f[q][w]);
	check(q+1,w,f[q][w]);
	check(q,w-1,f[q][w]);
	check(q,w+1,f[q][w]);
}
void chk(int q, int w, int rr){
	if(q<1||q>a||w<1||w>b) return;
	if(bo[q][w]==0||bo[q][w]==rr) return;
	v[bo[q][w]].push_back(rr);
	v[rr].push_back(bo[q][w]);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=a; i++){
		cin>>s;
		for(j=0; j<b; j++){
			if(s[j]=='B'){
				f[i][j+1]=1;
			}
			if(s[j]=='T'){
				f[i][j+1]=2;
			}
		}
	}
	for(i=1; i<=a; i++){
		for(j=1; j<=b; j++){
			if(f[i][j]==0||bo[i][j]!=0) continue;
			cnt++;
			dfs(i,j);
		}
	}
	for(i=1; i<=a; i++){
		for(j=1; j<=b; j++){
			if(bo[i][j]==0) continue;
			chk(i-1,j,bo[i][j]);
			chk(i+1,j,bo[i][j]);
			chk(i,j-1,bo[i][j]);
			chk(i,j+1,bo[i][j]);
		}
	}
	de.push_back(bo[1][1]);
	dis[bo[1][1]]=1;
	zx=1;
	while(de.size()){
		c=de.front();
		zx=max(zx,dis[c]);
		de.pop_front();
		for(vector <int>::iterator it=v[c].begin(); it!=v[c].end(); it++){
			if(dis[(*it)]==0){
				dis[(*it)]=dis[c]+1;
				de.push_back((*it));
			}
		}
	}
	cout<<zx;
	return 0;
}

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