Mixing
find the shortest path between two points with obstacles
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 '18 at 7:23
flashflash
198217
add a comment |
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 '18 at 7:23
flashflash
198217
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
See this answer.
– John McClane
Nov 21 '18 at 2:32
add a comment |
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 '18 at 7:23
flashflash
198217
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
java algorithm data-structures breadth-first-search
asked Nov 20 '18 at 7:23
flashflash
198217
asked Nov 20 '18 at 7:23
flashflash
198217
edited Nov 27 '18 at 2:19
flash
asked Nov 20 '18 at 7:23
flashflash
198217
asked Nov 20 '18 at 7:23
flashflash
198217
asked Nov 20 '18 at 7:23
flashflash
198217
198217
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
See this answer.
– John McClane
Nov 21 '18 at 2:32
add a comment |
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
See this answer.
– John McClane
Nov 21 '18 at 2:32
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
See this answer.
– John McClane
Nov 21 '18 at 2:32
See this answer.
– John McClane
Nov 21 '18 at 2:32
add a comment |
1 Answer
1
active
oldest
votes
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
add a comment |
Your Answer
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: "1"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fstackoverflow.com%2fquestions%2f53388098%2ffind-the-shortest-path-between-two-points-with-obstacles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
add a comment |
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
add a comment |
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
answered Nov 20 '18 at 10:25
Golam Rahman TusharGolam Rahman Tushar
686
686
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53388098%2ffind-the-shortest-path-between-two-points-with-obstacles%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
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 '18 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 '18 at 7:38
See this answer.
– John McClane
Nov 21 '18 at 2:32