Shortest Cell Path In a given grid The Next CEO of Stack OverflowHackerRank - The Grid Searchgoogle foo.bar max path algorithm puzzle optimizationBFS shortest path for Google Foobar “Prepare the Bunnies' Escape”Shortest Path For Google Foobar (Prepare The Bunnies Escape)Shortest path around a set of pointsShortest path challengeFinding nodes around a given node in a gridAdd an edge to a graph to minimize the average shortest path lengthGoogle FooBar “Prepare The Bunnies Escape”Find Shortest Word Edit Path in python

Is it correct to say moon starry nights?

Which acid/base does a strong base/acid react when added to a buffer solution?

Why do we say “un seul M” and not “une seule M” even though M is a “consonne”?

Identify and count spells (Distinctive events within each group)

My boss doesn't want me to have a side project

Can I cast Thunderwave and be at the center of its bottom face, but not be affected by it?

How to coordinate airplane tickets?

Upgrading From a 9 Speed Sora Derailleur?

pgfplots: How to draw a tangent graph below two others?

Could a dragon use its wings to swim?

Can you teleport closer to a creature you are Frightened of?

Is it a bad idea to plug the other end of ESD strap to wall ground?

Is a linearly independent set whose span is dense a Schauder basis?

Does int main() need a declaration on C++?

Early programmable calculators with RS-232

Planeswalker Ability and Death Timing

Arrows in tikz Markov chain diagram overlap

Prodigo = pro + ago?

Is it okay to majorly distort historical facts while writing a fiction story?

Could a dragon use hot air to help it take off?

Gödel's incompleteness theorems - what are the religious implications?

Is it possible to create a QR code using text?

My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?

Ising model simulation



Shortest Cell Path In a given grid



The Next CEO of Stack OverflowHackerRank - The Grid Searchgoogle foo.bar max path algorithm puzzle optimizationBFS shortest path for Google Foobar “Prepare the Bunnies' Escape”Shortest Path For Google Foobar (Prepare The Bunnies Escape)Shortest path around a set of pointsShortest path challengeFinding nodes around a given node in a gridAdd an edge to a graph to minimize the average shortest path lengthGoogle FooBar “Prepare The Bunnies Escape”Find Shortest Word Edit Path in python










0












$begingroup$


I was given this problem in a mock interview. Would appreciate some code review for my implementation.




Shortest Cell Path In a given grid of 0s and 1s, we have some starting
row and column sr, sc and a target row and column tr, tc. Return the
length of the shortest path from sr, sc to tr, tc that walks along 1
values only.



Each location in the path, including the start and the end, must be a
1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.



It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the
starting and target positions are different.



If the task is impossible, return -1.



Examples:



input: grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]] sr = 0, sc =
0, tr = 2, tc = 0 output: 8 (The lines below represent this grid:)
1111 0001 1111



grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]] sr = 0, sc = 0, tr =
2, tc = 0 output: -1 (The lines below represent this grid:) 1111 0001
1011




def shortestCellPath(grid, sr, sc, tr, tc):
"""
@param grid: int[][]
@param sr: int
@param sc: int
@param tr: int
@param tc: int
@return: int
"""
path_lengths = []
shortestCellPathHelper(grid, sr, sc, tr, tc, 0, path_lengths)

return -1 if len(path_lengths) == 0 else min(path_lengths)

def shortestCellPathHelper(grid, r, c, tr, tc, path_len, path_lengths):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
return

if grid[r][c] != 1:
return

if r == tr and c == tc:
path_lengths.append(path_len)
return

grid[r][c] = -1

#4 directions
shortestCellPathHelper(grid, r, c - 1, tr, tc, path_len + 1, path_lengths)
shortestCellPathHelper(grid, r, c + 1, tr, tc, path_len + 1, path_lengths)
shortestCellPathHelper(grid, r - 1, c, tr, tc, path_len + 1, path_lengths)
shortestCellPathHelper(grid, r + 1, c, tr, tc, path_len + 1, path_lengths)









share|improve this question









$endgroup$
















    0












    $begingroup$


    I was given this problem in a mock interview. Would appreciate some code review for my implementation.




    Shortest Cell Path In a given grid of 0s and 1s, we have some starting
    row and column sr, sc and a target row and column tr, tc. Return the
    length of the shortest path from sr, sc to tr, tc that walks along 1
    values only.



    Each location in the path, including the start and the end, must be a
    1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.



    It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the
    starting and target positions are different.



    If the task is impossible, return -1.



    Examples:



    input: grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]] sr = 0, sc =
    0, tr = 2, tc = 0 output: 8 (The lines below represent this grid:)
    1111 0001 1111



    grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]] sr = 0, sc = 0, tr =
    2, tc = 0 output: -1 (The lines below represent this grid:) 1111 0001
    1011




    def shortestCellPath(grid, sr, sc, tr, tc):
    """
    @param grid: int[][]
    @param sr: int
    @param sc: int
    @param tr: int
    @param tc: int
    @return: int
    """
    path_lengths = []
    shortestCellPathHelper(grid, sr, sc, tr, tc, 0, path_lengths)

    return -1 if len(path_lengths) == 0 else min(path_lengths)

    def shortestCellPathHelper(grid, r, c, tr, tc, path_len, path_lengths):
    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
    return

    if grid[r][c] != 1:
    return

    if r == tr and c == tc:
    path_lengths.append(path_len)
    return

    grid[r][c] = -1

    #4 directions
    shortestCellPathHelper(grid, r, c - 1, tr, tc, path_len + 1, path_lengths)
    shortestCellPathHelper(grid, r, c + 1, tr, tc, path_len + 1, path_lengths)
    shortestCellPathHelper(grid, r - 1, c, tr, tc, path_len + 1, path_lengths)
    shortestCellPathHelper(grid, r + 1, c, tr, tc, path_len + 1, path_lengths)









    share|improve this question









    $endgroup$














      0












      0








      0





      $begingroup$


      I was given this problem in a mock interview. Would appreciate some code review for my implementation.




      Shortest Cell Path In a given grid of 0s and 1s, we have some starting
      row and column sr, sc and a target row and column tr, tc. Return the
      length of the shortest path from sr, sc to tr, tc that walks along 1
      values only.



      Each location in the path, including the start and the end, must be a
      1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.



      It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the
      starting and target positions are different.



      If the task is impossible, return -1.



      Examples:



      input: grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]] sr = 0, sc =
      0, tr = 2, tc = 0 output: 8 (The lines below represent this grid:)
      1111 0001 1111



      grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]] sr = 0, sc = 0, tr =
      2, tc = 0 output: -1 (The lines below represent this grid:) 1111 0001
      1011




      def shortestCellPath(grid, sr, sc, tr, tc):
      """
      @param grid: int[][]
      @param sr: int
      @param sc: int
      @param tr: int
      @param tc: int
      @return: int
      """
      path_lengths = []
      shortestCellPathHelper(grid, sr, sc, tr, tc, 0, path_lengths)

      return -1 if len(path_lengths) == 0 else min(path_lengths)

      def shortestCellPathHelper(grid, r, c, tr, tc, path_len, path_lengths):
      if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
      return

      if grid[r][c] != 1:
      return

      if r == tr and c == tc:
      path_lengths.append(path_len)
      return

      grid[r][c] = -1

      #4 directions
      shortestCellPathHelper(grid, r, c - 1, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r, c + 1, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r - 1, c, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r + 1, c, tr, tc, path_len + 1, path_lengths)









      share|improve this question









      $endgroup$




      I was given this problem in a mock interview. Would appreciate some code review for my implementation.




      Shortest Cell Path In a given grid of 0s and 1s, we have some starting
      row and column sr, sc and a target row and column tr, tc. Return the
      length of the shortest path from sr, sc to tr, tc that walks along 1
      values only.



      Each location in the path, including the start and the end, must be a
      1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.



      It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the
      starting and target positions are different.



      If the task is impossible, return -1.



      Examples:



      input: grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]] sr = 0, sc =
      0, tr = 2, tc = 0 output: 8 (The lines below represent this grid:)
      1111 0001 1111



      grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]] sr = 0, sc = 0, tr =
      2, tc = 0 output: -1 (The lines below represent this grid:) 1111 0001
      1011




      def shortestCellPath(grid, sr, sc, tr, tc):
      """
      @param grid: int[][]
      @param sr: int
      @param sc: int
      @param tr: int
      @param tc: int
      @return: int
      """
      path_lengths = []
      shortestCellPathHelper(grid, sr, sc, tr, tc, 0, path_lengths)

      return -1 if len(path_lengths) == 0 else min(path_lengths)

      def shortestCellPathHelper(grid, r, c, tr, tc, path_len, path_lengths):
      if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
      return

      if grid[r][c] != 1:
      return

      if r == tr and c == tc:
      path_lengths.append(path_len)
      return

      grid[r][c] = -1

      #4 directions
      shortestCellPathHelper(grid, r, c - 1, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r, c + 1, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r - 1, c, tr, tc, path_len + 1, path_lengths)
      shortestCellPathHelper(grid, r + 1, c, tr, tc, path_len + 1, path_lengths)






      python






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked 11 mins ago









      NinjaGNinjaG

      893633




      893633




















          0






          active

          oldest

          votes












          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216699%2fshortest-cell-path-in-a-given-grid%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216699%2fshortest-cell-path-in-a-given-grid%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          कुँवर स्रोत दिक्चालन सूची"कुँवर""राणा कुँवरके वंशावली"

          Why is a white electrical wire connected to 2 black wires?How to wire a light fixture with 3 white wires in box?How should I wire a ceiling fan when there's only three wires in the box?Two white, two black, two ground, and red wire in ceiling box connected to switchWhy is there a white wire connected to multiple black wires in my light box?How to wire a light with two white wires and one black wireReplace light switch connected to a power outlet with dimmer - two black wires to one black and redHow to wire a light with multiple black/white/green wires from the ceiling?Ceiling box has 2 black and white wires but fan/ light only has 1 of eachWhy neutral wire connected to load wire?Switch with 2 black, 2 white, 2 ground and 1 red wire connected to ceiling light and a receptacle?

          चैत्य भूमि चित्र दीर्घा सन्दर्भ बाहरी कडियाँ दिक्चालन सूची"Chaitya Bhoomi""Chaitya Bhoomi: Statue of Equality in India""Dadar Chaitya Bhoomi: Statue of Equality in India""Ambedkar memorial: Centre okays transfer of Indu Mill land"चैत्यभमि