Submission #1289345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289345		muhammad-ahmad	Tracks in the Snow (BOI13_tracks)	C++20	5 / 100	2116 ms	387004 KiB

tracks

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 4005;
int n, m, vis[N][N];
string s[N];
vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

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

vector<pair<int, int>> bfs(vector<pair<int, int>> C){
	queue<pair<int, int>> q;
	vector<pair<int, int>> c, ans;
	for (auto i : C) q.push(i);
	
	while (q.size()){
		auto [x, y] = q.front(); q.pop();
		c.push_back({x, y});
		for (auto ddx : dx){
			for (auto ddy : dy){
				int cx = x + ddx, cy = y + ddy;
				if (check(cx, cy) && s[cx][cy] == s[x][y]){
					vis[cx][cy] = 1;
					q.push({cx, cy});
				}
			}
		}
	}
	
	// for (int i = 1; i <= n; i++){
		// for (int j = 1; j <= m; j++) cout << vis[i][j] << ' ';
		// cout << endl;
	// }
	
	map<pair<int, int>, bool> B;

	
	for (auto [x, y] : c){
		// cout << x << ' ' << y << endl;
		for (auto ddx : dx){
			for  (auto ddy : dy){
				int cx = x + ddx, cy = y + ddy;
				if (!B[{cx, cy}] && check(cx, cy) && s[cx][cy] != s[x][y]){
					ans.push_back({cx, cy});
					B[{cx, cy}] = 1;
				}
			}
		}
	}
	 
	return ans;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> s[i];
		s[i] = "." + s[i];
	}
	
	
	s[1][0] = s[1][1];
	vector<pair<int, int>> t = {{1, 0}};
	int ans = 0;
	while (t.size()){
		t = bfs(t);
		// for (auto i : t) cout << i.first << ' ' << i.second << endl;
		// cout << endl;
		ans++;
	}
	
	cout << ans << endl;
	
	return;
}

signed main() {
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

• Subtask 1: 5 / 30
• Subtask 2: 0 / 70