aboutsummaryrefslogtreecommitdiff
path: root/where_will_ball_fall.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /where_will_ball_fall.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'where_will_ball_fall.cpp')
-rw-r--r--where_will_ball_fall.cpp50
1 files changed, 50 insertions, 0 deletions
diff --git a/where_will_ball_fall.cpp b/where_will_ball_fall.cpp
new file mode 100644
index 0000000..ee859b7
--- /dev/null
+++ b/where_will_ball_fall.cpp
@@ -0,0 +1,50 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<int> findBall(vvd(int) & grid) {
+ int m = grid.size(), n = grid[0].size();
+ vvd(int) ugrid(m * 3, vector<int>(n * 3));
+ for (auto i = 0; i < m; i++)
+ for (auto j = 0; j < n; j++) {
+ ugrid[i * 3 + 1][j * 3 + 1] = 1;
+ ugrid[i * 3][j * 3] = ugrid[i * 3 + 2][j * 3 + 2] = grid[i][j] == 1;
+ ugrid[i * 3][j * 3 + 2] = ugrid[i * 3 + 2][j * 3] = grid[i][j] != 1;
+ }
+ vector<int> ans;
+ for (auto i = 0; i < n; ++i)
+ ans.push_back(drop(i * 3 + 1, ugrid, m * 3, n * 3));
+ return ans;
+ }
+
+private:
+ vector<pair<int, int>> dir{{1, 0}, {0, -1}, {0, 1}};
+ int drop(int pos, vvd(int) & ugrid, int m, int n) {
+ queue<pair<int, int>> qp;
+ qp.push({0, pos});
+ while (!qp.empty()) {
+ auto [i, j] = qp.front();
+ qp.pop();
+ if (i == m - 1)
+ return j / 3;
+ ugrid[i][j] = 1;
+ for (auto [di, dj] : dir)
+ if (j + dj >= 0 && j + dj < n && !ugrid[i + di][j + dj]) {
+ qp.push({i + di, j + dj});
+ break;
+ }
+ }
+ return -1;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) grid = {{1, 1, 1, -1, -1},
+ {1, 1, 1, -1, -1},
+ {-1, -1, -1, 1, 1},
+ {1, 1, 1, 1, -1},
+ {-1, -1, -1, -1, -1}};
+ for (auto i : obj.findBall(grid))
+ cout << i << ' ';
+}