제출 #1076900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076900		poconut	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	765 ms	222160 KiB

tracks

#include"bits/stdc++.h"
#ifndef LOCAL
#define LINE
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#else
#define LINE cerr << "----------" << nl;
#define fastio
#endif
using namespace std;
using ll = long long; using ld = long double;
#define nl '\n'
#define arr array
#define pb push_back
#define S second
#define F first
#define int long long

const ll inf = 1e9+5;

void solve() {
	int n,m; cin >> n >> m;
	vector<string> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	deque<arr<int, 2>> q;
	vector dis(n, vector<int>(m, -1));
	int ans = 1;
	auto ok = [&] (int x, int y) {
		return x >=0 && x < n && y>=0 && y<m && dis[x][y] == -1 && a[x][y] != '.';
	};
	const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
	dis[0][0] = 1;
	q.push_front({0,0});
	while (q.size()) {
		auto [x, y] = q.front();
		q.pop_front();
		for (int k=0; k<4; k++) {
			int xx = x+dx[k], yy = y+dy[k];
			if (ok(xx, yy)) {
				if (a[xx][yy]!=a[x][y]) {
					dis[xx][yy] = dis[x][y]+1;
					q.push_back({xx, yy});
				} else {
					dis[xx][yy] = dis[x][y];
					q.push_front({xx, yy});
				}
			}
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			ans = max(ans, dis[i][j]);
		}
	}
	cout << ans << nl;
}

int32_t main() {
	/*
	freopen("swap.in", "r", stdin);
	freopen("swap.out", "w", stdout);
	*/
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
		LINE
	}
    return 0;
}

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