Submission #642963

#	Time	Username	Problem	Language	Result	Execution time	Memory
642963		ymm	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	617 ms	151160 KiB

tracks

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 4010;
char s[N][N];
int dis[N][N];
int h, w;

bool in(int x, int y) {return 0 <= x && x < h && 0 <= y && y < w && s[x][y] != '.';}

void bfs()
{
	Loop (i,0,N) Loop (j,0,N)
		dis[i][j] = 1e9+10;
	dis[0][0] = 0;
	deque<pair<pii,int>> q;
	q.push_back({{0,0},0});
	while (q.size()) {
		auto [dard, d] = q.front();
		auto [i, j] = dard;
		q.pop_front();
		if (d != dis[i][j])
			continue;
		for (auto [x, y] : {pii{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
			x += i; y += j;
			if (!in(x, y))
				continue;
			int w = s[i][j] != s[x][y];
			if (dis[x][y] <= d + w)
				continue;
			dis[x][y] = d + w;
			if (w == 0)
				q.push_front({{x, y}, d + w});
			else
				q.push_back( {{x, y}, d + w});
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> h >> w;
	Loop (i,0,h)
		cin >> s[i];
	bfs();
	int ans = 0;
	Loop (i,0,h) Loop (j,0,w)
		if (in(i, j))
			ans = max(ans, dis[i][j]);
	cout << ans+1 << '\n';
}

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