Submission #229216

#	Time	Username	Problem	Language	Result	Execution time	Memory
229216		VEGAnn	Zoo (COCI19_zoo)	C++14	110 / 110	67 ms	6328 KiB

zoo

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define pii pair<int, int>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 1010;
typedef long long ll;
queue<pii> q[2];
char c[N][N];
int n, m, mrk[N][N], tt = 0, st, ans = 0, step[4][2];
string pt = "BT";

void rec(int x, int y){
	if (c[x][y] == pt[st ^ 1] || c[x][y] == '*' || mrk[x][y] == tt)
		return;
	mrk[x][y] = tt;
	c[x][y] = 'N';
	
	if (x > 0) rec(x - 1, y);
	if (y > 0) rec(x, y - 1);
	if (y < m - 1) rec(x, y + 1);
	if (x < n - 1) rec(x + 1, y);
}

int main(){
	
	ios_base::sync_with_stdio(0); cin.tie(0);
	
//	freopen("in.txt","r",stdin);
	
	step[0][0] = 1; step[0][1] = 0;
	step[1][0] = -1; step[1][1] = 0;
	step[2][0] = 0; step[2][1] = 1;
	step[3][0] = 0; step[3][1] = -1;
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> c[i][j];
	
	st = pt.find(c[0][0]);
		
	q[st].push(MP(0, 0));
	mrk[0][0] = 1;
	
	for (;; st ^= 1){
		if (!sz(q[st])) break;
		
		ans++;
		
		while (sz(q[st])){
			pii cr = q[st].front(); q[st].pop();
			int x = cr.ft, y = cr.sd;
			
//			cerr << x << " " << y << '\n';
			
			for (int it = 0; it < 4; it++){
				int cx = x + step[it][0];
				int cy = y + step[it][1];
				
				if (cx >= 0 && cy >= 0 && cx < n && cy < m && 
					!mrk[cx][cy] && c[cx][cy] != '*'){
						mrk[cx][cy] = 1;
						q[pt.find(c[cx][cy])].push(MP(cx, cy));
					}
			}
		}
	}
	
	cout << ans;
}

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