Shortest Cell Path In a given gridHackerRank - The Grid Searchgoogle foo.bar max path algorithm puzzle...
Why CLRS example on residual networks does not follows its formula?
Email Account under attack (really) - anything I can do?
What Brexit solution does the DUP want?
Is Social Media Science Fiction?
cryptic clue: mammal sounds like relative consumer (8)
Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)
Closed subgroups of abelian groups
N.B. ligature in Latex
Why was the small council so happy for Tyrion to become the Master of Coin?
Is it possible to make sharp wind that can cut stuff from afar?
How do you conduct xenoanthropology after first contact?
I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine
What makes Graph invariants so useful/important?
What does "enim et" mean?
Simulate Bitwise Cyclic Tag
Copycat chess is back
Calculus Optimization - Point on graph closest to given point
Why do we use polarized capacitor?
Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).
What are these boxed doors outside store fronts in New York?
What is the meaning of "of trouble" in the following sentence?
Infinite past with a beginning?
Can a German sentence have two subjects?
A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?
Shortest Cell Path In a given grid
HackerRank - 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
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom: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)
python
asked Apr 2 at 6:40
NinjaGNinjaG
903633
$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
asked Apr 2 at 6:40
NinjaGNinjaG
903633
$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
asked Apr 2 at 6:40
NinjaGNinjaG
903633
$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 Apr 2 at 6:40
NinjaGNinjaG
903633
asked Apr 2 at 6:40
NinjaGNinjaG
903633
asked Apr 2 at 6:40
NinjaGNinjaG
903633
asked Apr 2 at 6:40
NinjaGNinjaG
903633
asked Apr 2 at 6:40
NinjaGNinjaG
903633
903633
add a comment |
add a comment |
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
});
}
});
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
