## 1033. Moving Stones Until Consecutive

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

## 1034. Coloring A Border

Solution: DFS

Time complexity: O(mn)
Space complexity: O(mn)

## 1035. Uncrossed Lines

Solution: LCS

Time complexity: O(nm)
Space complexity: O(mn)

## 1036. Escape a Large Maze

Solution: limited search

Time complexity: O(b^2)
Space complexity: O(b^2)

## C++

// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode