BFS C++ solution


#1
bool valid(int x, int y, int n, int m)
{
	if (x > 0 && y > 0 && x <= n && y <= m)
	{
		return true;
	}
	return false;
}
int Solution::knight(int A, int B, int C, int D, int E, int F)
{
	bool visited[A + 1][B + 1];
	int moves[A + 1][B + 1];
	memset(moves, -1, sizeof(moves));
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> Q;
	Q.push(make_pair(C, D));
	visited[C][D] = true;
	moves[C][D] = 0;
	while (!Q.empty())
	{
		pair<int, int> curr = Q.front();
		Q.pop();
		vector<pair<int, int>> graph;
		int x = curr.first, y = curr.second;
		if (valid(x - 1, y - 2, A, B)) graph.push_back(make_pair(x - 1, y - 2));
		if (valid(x - 1, y + 2, A, B)) graph.push_back(make_pair(x - 1, y + 2));
		if (valid(x + 1, y - 2, A, B)) graph.push_back(make_pair(x + 1, y - 2));
		if (valid(x + 1, y + 2, A, B)) graph.push_back(make_pair(x + 1, y + 2));
		if (valid(x + 2, y - 1, A, B)) graph.push_back(make_pair(x + 2, y - 1));
		if (valid(x + 2, y + 1, A, B)) graph.push_back(make_pair(x + 2, y + 1));
		if (valid(x - 2, y - 1, A, B)) graph.push_back(make_pair(x - 2, y - 1));
		if (valid(x - 2, y + 1, A, B)) graph.push_back(make_pair(x - 2, y + 1));
		for (auto a: graph)
		{
			int x1 = a.first, y1 = a.second;
			moves[x1][y1] = (moves[x1][y1] == -1) ? moves[x][y] + 1 : min(moves[x1][y1], moves[x][y] + 1);
			if (visited[x1][y1])
			{
				continue;
			}
			Q.push(make_pair(x1, y1));
			visited[x1][y1] = true;
		}
	}
	if (visited[E][F])
	{
		return moves[E][F];
	}
	return -1;
}