Submission #221189

#	Time	Username	Problem	Language	Result	Execution time	Memory
221189		eohomegrownapps	Zoo (COCI19_zoo)	C++14	110 / 110	60 ms	5248 KiB

zoo

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> animals; //0 - bull; 1 - tiger; 2 - visited

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int h,w;
int cntanimals(){
	bool animal = animals[0][0];
	queue<pair<int,int>> qcurr;
	queue<pair<int,int>> qnext;
	qcurr.push({0,0});
	animals[0][0]=2;
	int anicnt = 0;
	while (qcurr.size()>0){
		auto f = qcurr.front();
		qcurr.pop();
		int x = f.first;
		int y = f.second;
		//cout<<x<<" "<<y<<endl;
		for (int i = 0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if (!(0<=nx&&nx<w&&0<=ny&&ny<h)){
				continue;
			}
			if (animals[nx][ny]==animal){
				animals[nx][ny]=2;
				qcurr.push({nx,ny});
			} else if (animals[nx][ny]==!animal){
				animals[nx][ny]=2;
				qnext.push({nx,ny});
			}
		}
		if (qcurr.size()==0){
			//cout<<"===="<<endl;
			swap(qnext,qcurr);
			animal=!animal;
			anicnt++;
		}
	}
	return anicnt;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>h>>w;
	animals.resize(w,vector<int>(h,2));
	for (int y = 0; y<h; y++){
		for (int x = 0; x<w; x++){
			char c;
			cin>>c;
			if (c=='B'){
				animals[x][y]=0;
			} else if (c=='T'){
				animals[x][y]=1;
			}
		}
	}
	cout<<cntanimals()<<endl;
	return 0;
}

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