{"id":7652,"date":"2020-11-14T11:46:45","date_gmt":"2020-11-14T19:46:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7652"},"modified":"2020-11-14T11:49:25","modified_gmt":"2020-11-14T19:49:25","slug":"leetcode-1654-minimum-jumps-to-reach-home","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1654-minimum-jumps-to-reach-home\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1654. Minimum Jumps to Reach Home"},"content":{"rendered":"\n<p>A certain bug&#8217;s home is on the x-axis at position&nbsp;<code>x<\/code>. Help them get there from position&nbsp;<code>0<\/code>.<\/p>\n\n\n\n<p>The bug jumps according to the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>It can jump exactly&nbsp;<code>a<\/code>&nbsp;positions&nbsp;<strong>forward<\/strong>&nbsp;(to the right).<\/li><li>It can jump exactly&nbsp;<code>b<\/code>&nbsp;positions&nbsp;<strong>backward<\/strong>&nbsp;(to the left).<\/li><li>It cannot jump backward twice in a row.<\/li><li>It cannot jump to any&nbsp;<code>forbidden<\/code>&nbsp;positions.<\/li><\/ul>\n\n\n\n<p>The bug may jump forward&nbsp;<strong>beyond<\/strong>&nbsp;its home, but it&nbsp;<strong>cannot jump<\/strong>&nbsp;to positions numbered with&nbsp;<strong>negative<\/strong>&nbsp;integers.<\/p>\n\n\n\n<p>Given an array of integers&nbsp;<code>forbidden<\/code>, where&nbsp;<code>forbidden[i]<\/code>&nbsp;means that the bug cannot jump to the position&nbsp;<code>forbidden[i]<\/code>, and integers&nbsp;<code>a<\/code>,&nbsp;<code>b<\/code>, and&nbsp;<code>x<\/code>, return&nbsp;<em>the minimum number of jumps needed for the bug to reach its home<\/em>. If there is no possible sequence of jumps that lands the bug on position&nbsp;<code>x<\/code>, return&nbsp;<code>-1.<\/code><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> 3 jumps forward (0 -&gt; 3 -&gt; 6 -&gt; 9) will get the bug home.\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> forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11\n<strong>Output:<\/strong> -1\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> One jump forward (0 -&gt; 16) then one jump backward (16 -&gt; 7) will get the bug home.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= forbidden.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= a, b, forbidden[i] &lt;= 2000<\/code><\/li><li><code>0 &lt;= x &lt;= 2000<\/code><\/li><li>All the elements in&nbsp;<code>forbidden<\/code>&nbsp;are distinct.<\/li><li>Position&nbsp;<code>x<\/code>&nbsp;is not forbidden.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: BFS<\/strong><\/h2>\n\n\n\n<p>Normal BFS with two tricks:<br>1. For each position, we need to track whether it&#8217;s reached via a forward jump or backward jump<br>2. How far should we go? If we don&#8217;t limit, it can go forever which leads to TLE\/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that&#8217;s maximum distance we can jump back to home in one shot.<\/p>\n\n\n\n<p>Time complexity: O(max_distance * 2)<br>Space complexity: O(max_distance * 2)<\/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  int minimumJumps(vector<int>& forbidden, int a, int b, int x) {\n    constexpr int kMaxPosition = 4000;\n    if (x == 0) return 0;\n    queue<pair<int, bool>> q{{{0, true}}};\n    unordered_set<int> seen1, seen2;\n    for (int f : forbidden) seen1.insert(f), seen2.insert(f);\n    seen1.insert(0);\n    int steps = 0;\n    while (!q.empty()) {      \n      int size = q.size();\n      while (size--) {\n        auto [cur, forward] = q.front(); q.pop();        \n        if (cur == x) return steps;\n        if (cur > kMaxPosition) continue; \/\/ no way to go back\n        if (seen1.insert(cur + a).second)      \n          q.emplace(cur + a, true);\n        if (cur - b >= 0 && forward && seen2.insert(cur - b).second)\n          q.emplace(cur - b, false);\n      }\n      ++steps;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A certain bug&#8217;s home is on the x-axis at position&nbsp;x. Help them get there from position&nbsp;0. The bug jumps according to the following rules: It&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[34,177,42,668],"class_list":["post-7652","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-medium","tag-search","tag-steps","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7652","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=7652"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7652\/revisions"}],"predecessor-version":[{"id":7654,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7652\/revisions\/7654"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7652"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7652"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7652"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}