{"id":6423,"date":"2020-03-08T12:49:39","date_gmt":"2020-03-08T19:49:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6423"},"modified":"2020-03-10T22:32:33","modified_gmt":"2020-03-11T05:32:33","slug":"leetcode-1377-frog-position-after-t-seconds","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1377-frog-position-after-t-seconds\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1377. Frog Position After T Seconds"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1377. Frog Position After T Seconds - \u5237\u9898\u627e\u5de5\u4f5c EP313\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/B5nDIxkoEyo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an undirected tree&nbsp;consisting of&nbsp;<code>n<\/code>&nbsp;vertices numbered from 1 to&nbsp;<code>n<\/code>. A frog starts jumping&nbsp;from the&nbsp;<strong>vertex 1<\/strong>. In one second, the frog&nbsp;jumps from its&nbsp;current&nbsp;vertex to another&nbsp;<strong>unvisited<\/strong>&nbsp;vertex if they are directly connected. The frog can not jump back to a visited vertex.&nbsp;In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.&nbsp;<\/p>\n\n\n\n<p>The edges of the undirected tree&nbsp;are given in the array&nbsp;<code>edges<\/code>, where&nbsp;<code>edges[i] = [from<sub>i<\/sub>, to<sub>i<\/sub>]<\/code>&nbsp;means that exists an edge connecting directly the vertices&nbsp;<code>from<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>to<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p><em>Return the probability that after&nbsp;<code>t<\/code>&nbsp;seconds the frog is on the vertex&nbsp;<code>target<\/code>.<\/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\/2020\/02\/20\/frog_2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4\n<strong>Output:<\/strong> 0.16666666666666666 \n<strong>Explanation: <\/strong>The figure above shows the given graph. The frog starts at vertex 1, jumping with 1\/3 probability to the vertex 2 after <strong>second 1<\/strong> and then jumping with 1\/2 probability to vertex 4 after <strong>second 2<\/strong>. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1\/3 * 1\/2 = 1\/6 = 0.16666666666666666. \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/02\/20\/frog_3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7\n<strong>Output:<\/strong> 0.3333333333333333\n<strong>Explanation: <\/strong>The figure above shows the given graph. The frog starts at vertex 1, jumping with 1\/3 = 0.3333333333333333 probability to the vertex 7 after <strong>second 1<\/strong>. \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> n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6\n<strong>Output:<\/strong> 0.16666666666666666\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 100<\/code><\/li><li><code>edges.length == n-1<\/code><\/li><li><code>edges[i].length == 2<\/code><\/li><li><code>1 &lt;= edges[i][0], edges[i][1] &lt;= n<\/code><\/li><li><code>1 &lt;= t&nbsp;&lt;= 50<\/code><\/li><li><code>1 &lt;= target&nbsp;&lt;= n<\/code><\/li><li>Answers within&nbsp;<code>10^-5<\/code>&nbsp;of the actual value will be accepted as correct.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: BFS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/03\/1373-ep313.png\" alt=\"\" class=\"wp-image-6463\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/03\/1373-ep313.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/03\/1373-ep313-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/03\/1373-ep313-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>key: if a node has children, the fog jumps to to children so the probability at current node will become 0.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/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  double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {\n    vector<double> p(n + 1);\n    p[1] = 1.0;\n    vector<vector<int>> g(n + 1);\n    for (const auto& e : edges) {\n      g[e[0]].push_back(e[1]);\n      g[e[1]].push_back(e[0]);\n    }\n    vector<int> seen(n + 1);\n    seen[1] = 1;\n    queue<int> q{{1}};\n    while (t--) {\n      int size = q.size();      \n      while (size--) {\n        int cur = q.front(); q.pop();\n        int children = 0;\n        for (int nxt : g[cur])\n          if (!seen[nxt]) ++children;\n        for (int nxt : g[cur])\n          if (!seen[nxt]++) {\n            q.push(nxt);\n            p[nxt] += p[cur] \/ children;\n          }\n        \/\/ key: fog jumps this node has children\n        if (children > 0) p[cur] = 0.0;\n      }\n    }\n    return p[target];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">class Solution:\n  def frogPosition(self, n: int, edges: List[List[int]],\n                   t: int, target: int) -&gt; float:\n    p = [0] + [1] + [0] * (n - 1)\n    seen = [False] + [True] + [False] * (n - 1)    \n    q = [1]\n    g = [[] for _ in range(n + 1)]\n    for i, j in edges:\n      g[i].append(j)\n      g[j].append(i)\n    for _ in range(t):\n      q2 = []\n      for cur in q:\n        children = sum([not seen[nxt] for nxt in g[cur]])\n        for nxt in g[cur]:\n          if seen[nxt]: continue\n          seen[nxt] = True\n          q2.append(nxt)\n          p[nxt] = p[cur] \/ children\n        if children &gt; 0: p[cur] = 0\n      q = q2\n    return p[target]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an undirected tree&nbsp;consisting of&nbsp;n&nbsp;vertices numbered from 1 to&nbsp;n. A frog starts jumping&nbsp;from the&nbsp;vertex 1. In one second, the frog&nbsp;jumps from its&nbsp;current&nbsp;vertex to another&nbsp;unvisited&nbsp;vertex if&#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,77,217,120],"class_list":["post-6423","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-graph","tag-hard","tag-probability","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6423","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=6423"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6423\/revisions"}],"predecessor-version":[{"id":6464,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6423\/revisions\/6464"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6423"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}