Submission #573047

#	Time	Username	Problem	Language	Result	Execution time	Memory
573047		fuad27	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	768 ms	386420 KiB

tracks

/*
 * Created: 2022-06-05 19:50
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string& s) {
	for(char i:s){
		os << i;
	}
	return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif
struct node {
	int x, y;
	int w;
	node() {
		w=0,x=0,y=0;
	}
};
int ax[] = {0, 0, 1, -1};
int ay[] = {1, -1, 0, 0};
void solve() {
	int n, m;cin >> n >> m;
	vector<string> v(n);
	rep(i,0,n)cin>>v[i];
	// ff -> 0, 1
	// ss -> x, y
	deque<node> dq;
	dq.push_back(node());
	vector<vector<bool>> vis(n, vector<bool> (m,0));
	ll ans = 1;
	while(!dq.empty()) {
		node at = dq.front();
		dq.pop_front();
		if(vis[at.x][at.y])continue;
		vis[at.x][at.y] = 1;
		ans = max(ans, (ll)at.w+1);
		for(int i = 0;i<4;i++) {
			if(at.x + ax[i] >= 0 && at.x + ax[i] < n && at.y + ay[i] >= 0 && at.y + ay[i] < m) {
				if(v[at.x+ax[i]][at.y+ay[i]]=='.')continue;
				if(v[at.x+ax[i]][at.y+ay[i]]==v[at.x][at.y]){
					node to = node();
					to.x=at.x + ax[i];
					to.y=at.y+ay[i];
					to.w = at.w;
					dq.push_front(to);
				}
				else {
					node to = node();
					to.x=at.x + ax[i];
					to.y=at.y+ay[i];
					to.w = at.w+1;
					dq.push_back(to);
				}
			}
		}
	}
	cout << ans << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//~ cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

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