Submission #554205

#	Time	Username	Problem	Language	Result	Execution time	Memory
554205		Karnis_052	Tracks in the Snow (BOI13_tracks)	C++17	4.38 / 100	760 ms	93424 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 vis[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];
	char color = grid[0][0];
	int ans = 0, f1 = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (vis[i][j]) continue;

			vis[i][j] = 1;
			if (grid[i][j] != color)
			{
				if (grid[i][j] != '.')
					f1 = 1;
				continue;
			}
			queue<pair<int, int>>qu;
			qu.push({i, j});
			while (!qu.empty())
			{
				auto node = qu.front();
				qu.pop();
				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] != color or vis[nx][ny])continue;
					vis[nx][ny] = 1;
					qu.push({nx, ny});
				}
			}
			ans = ans + 1 + f1;
			f1 = 0;

		}
	}
	cout << ans << endl;

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

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