In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false Explanation: The target square is inaccessible starting from the source square, because we can’t walk outside the grid. Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999] Output: true Explanation: Because there are no blocked cells, it’s possible to reach the target square.

boolbfs(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target){ unordered_set<long> set_blocked, set_visited; queue<pair<int,int>> q; for (auto &v : blocked) set_blocked.insert(get_index(v[0], v[1])); q.push({source[0], source[1]}); vector<vector<int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}}; int count = 1; while (!q.empty()) { auto p = q.front(); q.pop(); for (auto dir : dirs) { int x = p.first + dir[0]; int y = p.second + dir[1]; if (x < 0 || x >= 1000000 || y < 0 || y >= 1000000) continue; if (x == target[0] && y == target[1]) returntrue; long index = get_index(x, y); if (set_blocked.count(index) || set_visited.count(index)) continue; set_visited.insert(index); q.push({x,y});

if (count++ == 20000) returntrue; } } returnfalse; } longget_index(int x, int y){ return x * 1000000UL + y; } };