Submission #1145585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145585		WongYiKai	Zoo (COCI19_zoo)	C++20	110 / 110	108 ms	16724 KiB

zoo

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


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll r,c;
	cin >> r >> c;
	ll grid[1005][1005],visited[1005][1005];

	for (int i=0;i<r;i++){
		for (int j=0;j<c;j++){
			char temp;
			cin >> temp;
			if (temp=='T') grid[i][j] = 1;
			else if (temp=='B') grid[i][j] = 2;
			else grid[i][j] = 0;
			visited[i][j] = 0;
		}
	}

	ll dx[] = {0,0,1,-1};
	ll dy[] = {1,-1,0,0};

	priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq;
	pq.push({1,{0,0}});
	visited[0][0] = 1;
	ll high = 1;
	while (!pq.empty()){
		pair<ll,pair<ll,ll>> curr = pq.top();
		pq.pop();
		ll x = curr.second.first;
		ll y = curr.second.second;

		for (int i=0;i<4;i++){
			ll nx = x+dx[i], ny = y+dy[i];
			if (nx < 0 || ny < 0) continue;
			if (nx>=r || ny >= c) continue;
			if (visited[nx][ny] == 1) continue;
			if (grid[nx][ny] == 0) continue;
			if (grid[nx][ny] == grid[x][y]) pq.push({curr.first,{nx,ny}});
			else pq.push({curr.first+1,{nx,ny}});
			visited[nx][ny] = 1;
		}
		high = max(high,curr.first);
	}
	cout << high;
}

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