{"id":7864,"date":"2020-12-27T12:26:24","date_gmt":"2020-12-27T20:26:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7864"},"modified":"2020-12-27T12:28:45","modified_gmt":"2020-12-27T20:28:45","slug":"leetcode-1706-where-will-the-ball-fall","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1706-where-will-the-ball-fall\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1706. Where Will the Ball Fall"},"content":{"rendered":"\n<p>You have a 2-D&nbsp;<code>grid<\/code>&nbsp;of size&nbsp;<code>m x n<\/code>&nbsp;representing a box, and you have&nbsp;<code>n<\/code>&nbsp;balls. The box is open on the top and bottom sides.<\/p>\n\n\n\n<p>Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as&nbsp;<code>1<\/code>.<\/li><li>A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as&nbsp;<code>-1<\/code>.<\/li><\/ul>\n\n\n\n<p>We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a &#8220;V&#8221; shaped pattern between two boards or if a board redirects the ball into either wall of the box.<\/p>\n\n\n\n<p>Return&nbsp;<em>an array&nbsp;<\/em><code>answer<\/code><em>&nbsp;of size&nbsp;<\/em><code>n<\/code><em>&nbsp;where&nbsp;<\/em><code>answer[i]<\/code><em>&nbsp;is the column that the ball falls out of at the bottom after dropping the ball from the&nbsp;<\/em><code>i<sup>th<\/sup><\/code><em>&nbsp;column at the top, or&nbsp;<code>-1<\/code>&nbsp;if the ball gets stuck in the box.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/09\/26\/ball.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> 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]]\n<strong>Output:<\/strong> [1,-1,-1,-1,-1]\n<strong>Explanation:<\/strong> This example is shown in the photo.\nBall b0 is dropped at column 0 and falls out of the box at column 1.\nBall b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.\nBall b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.\nBall b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.\nBall b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[-1]]\n<strong>Output:<\/strong> [-1]\n<strong>Explanation:<\/strong> The ball gets stuck against the left wall.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 100<\/code><\/li><li><code>grid[i][j]<\/code>&nbsp;is&nbsp;<code>1<\/code>&nbsp;or&nbsp;<code>-1<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h2>\n\n\n\n<p>Figure out 4 conditions that the ball will get stuck.<\/p>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> findBall(vector<vector<int>>& G) {\n    const int m = G.size();\n    const int n = G[0].size();\n    auto fall = [&](int x) -> int {\n      for (int y = 0; y < m; ++y)\n        if ((G[y][x] == -1 &#038;&#038; (x == 0 || G[y][x - 1] == 1)) ||            \n            (G[y][x] == 1 &#038;&#038; (x == n - 1 || G[y][x + 1] == -1)))           \n          return -1;\n        else\n          x += G[y][x];      \n      return x;\n    };\n    vector<int> ans(n);\n    for (int x = 0; x < n; ++x)\n      ans[x] = fall(x);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You have a 2-D&nbsp;grid&nbsp;of size&nbsp;m x n&nbsp;representing a box, and you have&nbsp;n&nbsp;balls. The box is open on the top and bottom sides. Each cell in&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[],"class_list":["post-7864","post","type-post","status-publish","format-standard","hentry","category-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7864","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7864"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7864\/revisions"}],"predecessor-version":[{"id":7866,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7864\/revisions\/7866"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7864"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7864"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7864"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}