C++ BFS with comments


#1
bool isInCircle(int x, int y, int center_x, int center_y, int radius)
{
	return std::pow((x - center_x), 2) + std::pow((y - center_y), 2) <= std::pow(radius, 2);
}

bool isInCircles(int x, int y, vector<int> &E, vector<int> &F, int radius)
{
	for (int i = 0; i < E.size(); ++i)
	{
		if (isInCircle(x, y, E[i], F[i], radius))
		{
			return true;
		}
	}
	return false;
}

bool isInLimit(int m, int n, int x, int y)
{
	return m >= 0 && m <= x && n >= 0 && n <= y;
}
string Solution::solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F) {
	int radius = D;
	int num_circle = C;

	int x = A;
	int y = B;

	int s_x = 0;
	int s_y = 0;
	vector<pair<int, int>> delta = {
		make_pair(1, 0),
		make_pair(0, 1),
		make_pair(1, 1),
		make_pair(1, 0),
		make_pair(-1, 0),
		make_pair(-1, 1),
		make_pair(0, -1),
		make_pair(1, -1)
	};

	vector<vector<bool>> visited(x+1, vector<bool>(y+1, false));
	
	// mark visited all points within circles
	for (int i = 0; i <= x; ++i)
		for (int j = 0; j <= y; ++j)
		{
			if (isInCircles(i, j, E, F, radius))
			{
				visited[i][j] = true;
			}

		}
		
	// use set to ignore duplicates neighbours
	set<pair<int, int>> q;

	q.insert(make_pair(s_x, s_y));

	while (!q.empty())
	{
		pair<int, int> curr = *q.begin();
		q.erase(q.begin());
		visited[curr.first][curr.second] = true;
		
		// add neighbors
		for (auto p : delta)
		{
			int n_x = curr.first + p.first;
			int n_y = curr.second + p.second;

			if (isInLimit(n_x, n_y, x, y) && !visited[n_x][n_y])
			{
				if (n_x == x && n_y == y) //found
					return "YES";
				q.insert(make_pair(n_x, n_y));
			}
		}
	}

	return "NO";
}

#2

very Nice Code !! easy to understand!!