제출 #1290163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290163		AbdullahIshfaq	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	470 ms	224132 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 4002, cd[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
ll n, m, d[N][N], mx = 1;
char c[N][N];
deque<pair<ll, ll>> q;
void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> c[i];
	d[0][0] = 1;
	q.push_back({0, 0});
	while (!q.empty())
	{
		ll x, y;
		x = q.front().first;
		y = q.front().second;
		q.pop_front();
		mx = max(mx, d[x][y]);
		for (int i = 0; i < 4; i++)
		{
			ll nx = x + cd[i][0], ny = y + cd[i][1];
			if (nx < 0 or nx >= n or ny < 0 or ny >= m or c[nx][ny] == '.' or d[nx][ny])
			{
				continue;
			}
			if (c[nx][ny] == c[x][y])
			{
				d[nx][ny] = d[x][y];
				q.push_front({nx, ny});
			}
			else
			{
				d[nx][ny] = d[x][y] + 1;
				q.push_back({nx, ny});
			}
		}
	}
	cout << mx << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	// cin >> t;
	for (ll i = 1; i <= t; i++)
	{
		solve();
	}
}

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