Submission #660772

#TimeUsernameProblemLanguageResultExecution timeMemory
660772Koful123Zoo (COCI19_zoo)C++17
110 / 110
46 ms10328 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

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

void solve(){

	int n,m;
	cin >> n >> m;

	string grid[n];
	vector<vector<int>> vis(n,vector<int> (m));
	for(int i = 0; i < n; i++){
		cin >> grid[i];
		for(int j = 0; j < m; j++){
			if(grid[i][j] == '*'){
				vis[i][j] = 1;
			}
		}
	}

	auto check = [&](int x,int y){
		if(x < 0 || x >= n || y >= m || y < 0) return false;
		return !vis[x][y];
	};

	char c = grid[0][0]; int ans = 0;
	queue<pair<int,int>> q,nw; q.push({0,0});
	while(q.size()){
		while(q.size()){
			auto[x,y] = q.front(); q.pop();
			for(int i = 0; i < 4; i++){
				int curx = dx[i] + x,cury = dy[i] + y;
				if(check(curx,cury)){
					if(grid[curx][cury] == c) q.push({curx,cury}); 
					else nw.push({curx,cury});
					vis[curx][cury] = 1;
				}
			}
		}
		q = nw; ans++; while(nw.size()) nw.pop();
		c = (c == 'T' ? 'B' : 'T');
	}

	cout << ans << endl;
}
 
signed main(){	
 		
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...