Submission #888487

#	Time	Username	Problem	Language	Result	Execution time	Memory
888487		bashNewbie	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	570 ms	86004 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back

int n, m;
vs s; vi vis;
queue<int> q, nq;

inline bool in(int x) {
	return -1 < x && x < n*m;
}
inline bool bad(int x) {
	return s[x/m][x%m] == '.';
}
inline bool same(int x, int y) {
	return s[x/m][x%m] == s[y/m][y%m];
}
inline void put(int x, int y) {
	if(same(x, y)) q.push(y); else
	nq.push(y);
	vis[y] = 1;
}

int main() {
	fast_io;

	vvi adj = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

	cin >> n >> m;
	s = vs(n); for(auto &t: s) cin >> t;

	vis = vi(n*m); int ret = 0;
	q.push(0), vis[0] = 1;
	while(!q.empty()) {
		ret++; vi add;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			if(x%m > 0 && !vis[x-1] && !bad(x-1)) put(x, x-1);
			if(x%m<m-1 && !vis[x+1] && !bad(x+1)) put(x, x+1);
			if(x/m > 0 && !vis[x-m] && !bad(x-m)) put(x, x-m);
			if(x/m<n-1 && !vis[x+m] && !bad(x+m)) put(x, x+m);
		}
		while(!nq.empty()) {
			int x = nq.front(); nq.pop(), q.push(x);
		}
	}
	cout << ret << "\n";
}

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