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
$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)
python
$endgroup$
add a comment |
$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)
python
$endgroup$
add a comment |
$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)
python
$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
python
asked 11 mins ago
NinjaGNinjaG
893633
893633
add a comment |
add a comment |
0
active
oldest
votes
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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