Submission #471402

#	Time	Username	Problem	Language	Result	Execution time	Memory
471402		YoRepi7	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	877 ms	120908 KiB

tracks

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vpl = vector<pl>;
using vpi = vector<pi>;
using vc = vector<char>;
using vs = vector<string>;
 
#define forn(i, n) for(int i = 0; i < n; i++)
#define rofn(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, b, a) for(int i = b; i >= a; i--)
#define TRAV(a, x) for(auto& a: x)
#define ABC(c) for(char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<int>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (int)(x).length()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) TRAV(a, x) cout << a << " "
#define print(x) cout << x << endl
#define traverse(x) TRAV(a, x) cout << a.f << " " << a.s << endl
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)

const int MAXN = 4000;

int xDir[4] = {1, -1, 0, 0}, yDir[4] = {0, 0, 1, -1}, dist[MAXN][MAXN], h, w;
char grid[MAXN][MAXN];

bool ok(int i, int j){
	if(i >= h || j >= w || i < 0 || j < 0 || grid[i][j] == '.') return false;
	return true;
}

void solve(){
	cin >> h >> w;
	forn(i, h){
		forn(j, w){
			cin >> grid[i][j];
		}
	}
	int ans = 0;
	deque<pi> q;
	dist[0][0] = 1;
	q.push_front({0, 0});
	while(sz(q)){
		pi cur = q.front();
		q.pop_front();
		ans = max(ans, dist[cur.f][cur.s]);
		forn(i, 4){
			int x = cur.f + xDir[i], y = cur.s + yDir[i];
			if(ok(x, y) && dist[x][y] == 0){
				if(grid[cur.f][cur.s] == grid[x][y]){
					dist[x][y] = dist[cur.f][cur.s];
					q.push_front({x, y});
				} else {
					dist[x][y] = dist[cur.f][cur.s] + 1;
					q.push_back({x, y});
				}
			}
		}
	}
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	// int t; cin >> t;
	// forn(i, t){
	// 	solve();
	// }
	solve();
}

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