Submission #554206

#	Time	Username	Problem	Language	Result	Execution time	Memory
554206		Karnis_052	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	538 ms	89856 KiB

tracks

// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
typedef long long int  ll;
typedef pair<int, int>PI;
typedef pair<ll, ll > PL;
typedef vector<int>VI;
typedef vector<ll>VL;
#define FF first
#define SS second
const int mod = 1e9 + 7;
const int INF = 1e9;
const int N = 4e3 + 5;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dist[N][N];
int main()
{
	ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	char grid[n][m];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> grid[i][j];

	int ans = 0, f1 = 0;
	deque<pair<int, int>>qu;
	qu.push_front({0, 0});
	dist[0][0] = 1;
	while (!qu.empty())
	{
		auto node = qu.front();
		qu.pop_front();
		ans = max(ans, dist[node.FF][node.SS]);
		for (int d = 0; d < 4; d++)
		{
			int nx = node.FF + dx[d], ny = node.SS + dy[d];
			if (nx<0 or ny<0 or nx >= n or ny >= m or grid[nx][ny] != '.' or dist[nx][ny])continue;
			int ndist = dist[node.FF][node.SS] + (grid[node.FF][node.SS] != grid[nx][ny]);
			dist[nx][ny] = ndist;
			if (dist[nx][ny] == dist[node.FF][node.SS])
				qu.push_front({nx, ny});
			else qu.push_back({nx, ny});
		}
	}



	cout << ans << endl;

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:27:15: warning: unused variable 'f1' [-Wunused-variable]
   27 |  int ans = 0, f1 = 0;
      |               ^~

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