lc1036-逃离大迷宫

题目描述

• 原题

示例

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true

题解

• 思路：bfs
• golang 写得不好，先放 cpp 吧

class Solution {
public:unordered_set<string> s;int n = 1e6;int m;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {m = blocked.size();for (auto &b: blocked) s.insert(get(b));return bfs(source, target) && bfs(target, source);}string get(vector<int> p) {return to_string(p[0]) + ' ' + to_string(p[1]);}bool bfs(vector<int> &source, vector<int> &target) {auto st = s;queue<vector<int>> q;q.push(source);st.insert(get(source));int cnt = 1;while (q.size()) {auto t = q.front(); q.pop();for (int d = 0; d < 4; d ++ ) {int x = t[0] + dx[d], y = t[1] + dy[d];if (0 <= x && x < n && 0 <= y && y < n &&!st.count(get({x, y}))) {cnt ++ ;if (cnt * 2 > m * (m - 1)) return true;if (target[0] == x && target[1] == y) return true;q.push({x, y});st.insert(get({x, y}));}}}return false;}
};