Find out minimum steps to reach any corner of maze?
You have given a n*m maze (matrix) which contains values 0, 1 and 2 . value 0 means cell is open , value 1 means cell is block and value 2 is starting point. You can go only in left ,right ,top ,down direction in maze. Find out minimum distance from starting point to any corner of matrix .
Example :
n = 4, m = 5
maze :
1 1 1 0 1
1 0 2 0 1
1 0 1 0 1
0 0 1 0 1
Answer will be 2 .
path -> starting point(2 ,3)->(2,4)->(1,4).
Help me to solve this problem !!
algorithm data-structures backtracking maze
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
add a comment |
You have given a n*m maze (matrix) which contains values 0, 1 and 2 . value 0 means cell is open , value 1 means cell is block and value 2 is starting point. You can go only in left ,right ,top ,down direction in maze. Find out minimum distance from starting point to any corner of matrix .
Example :
n = 4, m = 5
maze :
1 1 1 0 1
1 0 2 0 1
1 0 1 0 1
0 0 1 0 1
Answer will be 2 .
path -> starting point(2 ,3)->(2,4)->(1,4).
Help me to solve this problem !!
algorithm data-structures backtracking maze
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
2
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
2
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17
add a comment |
You have given a n*m maze (matrix) which contains values 0, 1 and 2 . value 0 means cell is open , value 1 means cell is block and value 2 is starting point. You can go only in left ,right ,top ,down direction in maze. Find out minimum distance from starting point to any corner of matrix .
Example :
n = 4, m = 5
maze :
1 1 1 0 1
1 0 2 0 1
1 0 1 0 1
0 0 1 0 1
Answer will be 2 .
path -> starting point(2 ,3)->(2,4)->(1,4).
Help me to solve this problem !!
algorithm data-structures backtracking maze
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
You have given a n*m maze (matrix) which contains values 0, 1 and 2 . value 0 means cell is open , value 1 means cell is block and value 2 is starting point. You can go only in left ,right ,top ,down direction in maze. Find out minimum distance from starting point to any corner of matrix .
Example :
n = 4, m = 5
maze :
1 1 1 0 1
1 0 2 0 1
1 0 1 0 1
0 0 1 0 1
Answer will be 2 .
path -> starting point(2 ,3)->(2,4)->(1,4).
Help me to solve this problem !!
algorithm data-structures backtracking maze
algorithm data-structures backtracking maze
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
edited Nov 25 '18 at 18:23
Bishal Gautam
820517
820517
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
asked Nov 13 '18 at 5:58
Sandeep DanSandeep Dan
62
62
2
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
2
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17
add a comment |
2
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
2
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17
2
2
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
2
2
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17
add a comment |
1 Answer
1
active
oldest
votes
If you are familiar with BFS and already solved the following classic problem:
Calculate the shortest path from a starting point to ending point in 2D
grid with some obstacles!
then you can solve your problem by running BFS from starting point once and then going through all corner points having value 0 and comparing the minimum distance among them.
There can be several paths leading to minimum distance. If you want to trace the path then you can maintain another 2D grid for storing parent's information of each 2D point while performing BFS.
Please let me know if you face any problem while coding. Thanks!!
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
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%2f53274687%2ffind-out-minimum-steps-to-reach-any-corner-of-maze%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
If you are familiar with BFS and already solved the following classic problem:
Calculate the shortest path from a starting point to ending point in 2D
grid with some obstacles!
then you can solve your problem by running BFS from starting point once and then going through all corner points having value 0 and comparing the minimum distance among them.
There can be several paths leading to minimum distance. If you want to trace the path then you can maintain another 2D grid for storing parent's information of each 2D point while performing BFS.
Please let me know if you face any problem while coding. Thanks!!
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
add a comment |
If you are familiar with BFS and already solved the following classic problem:
Calculate the shortest path from a starting point to ending point in 2D
grid with some obstacles!
then you can solve your problem by running BFS from starting point once and then going through all corner points having value 0 and comparing the minimum distance among them.
There can be several paths leading to minimum distance. If you want to trace the path then you can maintain another 2D grid for storing parent's information of each 2D point while performing BFS.
Please let me know if you face any problem while coding. Thanks!!
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
add a comment |
If you are familiar with BFS and already solved the following classic problem:
Calculate the shortest path from a starting point to ending point in 2D
grid with some obstacles!
then you can solve your problem by running BFS from starting point once and then going through all corner points having value 0 and comparing the minimum distance among them.
There can be several paths leading to minimum distance. If you want to trace the path then you can maintain another 2D grid for storing parent's information of each 2D point while performing BFS.
Please let me know if you face any problem while coding. Thanks!!
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
If you are familiar with BFS and already solved the following classic problem:
Calculate the shortest path from a starting point to ending point in 2D
grid with some obstacles!
then you can solve your problem by running BFS from starting point once and then going through all corner points having value 0 and comparing the minimum distance among them.
There can be several paths leading to minimum distance. If you want to trace the path then you can maintain another 2D grid for storing parent's information of each 2D point while performing BFS.
Please let me know if you face any problem while coding. Thanks!!
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
answered Nov 25 '18 at 12:39
Bishal GautamBishal Gautam
820517
820517
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%2f53274687%2ffind-out-minimum-steps-to-reach-any-corner-of-maze%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
2
What have you learned? graph, Djikstra, shortest path?
– Surt
Nov 13 '18 at 6:09
just new in programming , I have just solved some basic problem related to graph(bfs ,dfs , mst) and also start learning backtracking . question comes in mind while solving rate in maze problem.
– Sandeep Dan
Nov 13 '18 at 6:14
2
So to solve this translate it to a graph, then use one of the algorithms that you have learned to find the shortest path.
– Surt
Nov 13 '18 at 6:17