Find the shortest path to reach a given destination cell in 2D matrix with obstacles












4















I am working on below interview question and I am confuse on how to use BFS search here. I am confuse on how to deal with the blockades here?




Given a MxN matrix find the shortest path to reach a given destination
cell. The robot can move up, down, left or right. The matrix also
comes with set of blockades in few of the cells where the robot can't
pass through. Output the minimum number of moves the robot needs to
make to reach the destination. Output -1 if the destination is not
reachable. Assume that the blockade will never be at the starting
cell.



Input Format: First line contains the values of M and N matrix. Second
line contains the cell location of the robots starting position. Third
line contains the cell location of the destination. Fourth line and
the lines following that will contain the locations of the blockades.
The example below contains only one blockade at (2,2) where the robot
can't pass through. Below is the input:




3 3
1 1
3 3
2 2


Output should be 4 for above input.



Below is what I have started but confuse on how to deal with blockades here while doing BFS search:



  public static void main(String args ) throws Exception {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();

int startX = sc.nextInt();
int startY = sc.nextInt();

int destinationX = sc.nextInt();
int destinationY = sc.nextInt();

while (sc.hasNext()) {
int blockedX = sc.nextInt();
int blockedY = sc.nextInt();
}
}









share|improve this question

























  • Note that you can also use depth first search for this.

    – vivek_23
    Nov 20 '18 at 6:26
















4















I am working on below interview question and I am confuse on how to use BFS search here. I am confuse on how to deal with the blockades here?




Given a MxN matrix find the shortest path to reach a given destination
cell. The robot can move up, down, left or right. The matrix also
comes with set of blockades in few of the cells where the robot can't
pass through. Output the minimum number of moves the robot needs to
make to reach the destination. Output -1 if the destination is not
reachable. Assume that the blockade will never be at the starting
cell.



Input Format: First line contains the values of M and N matrix. Second
line contains the cell location of the robots starting position. Third
line contains the cell location of the destination. Fourth line and
the lines following that will contain the locations of the blockades.
The example below contains only one blockade at (2,2) where the robot
can't pass through. Below is the input:




3 3
1 1
3 3
2 2


Output should be 4 for above input.



Below is what I have started but confuse on how to deal with blockades here while doing BFS search:



  public static void main(String args ) throws Exception {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();

int startX = sc.nextInt();
int startY = sc.nextInt();

int destinationX = sc.nextInt();
int destinationY = sc.nextInt();

while (sc.hasNext()) {
int blockedX = sc.nextInt();
int blockedY = sc.nextInt();
}
}









share|improve this question

























  • Note that you can also use depth first search for this.

    – vivek_23
    Nov 20 '18 at 6:26














4












4








4








I am working on below interview question and I am confuse on how to use BFS search here. I am confuse on how to deal with the blockades here?




Given a MxN matrix find the shortest path to reach a given destination
cell. The robot can move up, down, left or right. The matrix also
comes with set of blockades in few of the cells where the robot can't
pass through. Output the minimum number of moves the robot needs to
make to reach the destination. Output -1 if the destination is not
reachable. Assume that the blockade will never be at the starting
cell.



Input Format: First line contains the values of M and N matrix. Second
line contains the cell location of the robots starting position. Third
line contains the cell location of the destination. Fourth line and
the lines following that will contain the locations of the blockades.
The example below contains only one blockade at (2,2) where the robot
can't pass through. Below is the input:




3 3
1 1
3 3
2 2


Output should be 4 for above input.



Below is what I have started but confuse on how to deal with blockades here while doing BFS search:



  public static void main(String args ) throws Exception {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();

int startX = sc.nextInt();
int startY = sc.nextInt();

int destinationX = sc.nextInt();
int destinationY = sc.nextInt();

while (sc.hasNext()) {
int blockedX = sc.nextInt();
int blockedY = sc.nextInt();
}
}









share|improve this question
















I am working on below interview question and I am confuse on how to use BFS search here. I am confuse on how to deal with the blockades here?




Given a MxN matrix find the shortest path to reach a given destination
cell. The robot can move up, down, left or right. The matrix also
comes with set of blockades in few of the cells where the robot can't
pass through. Output the minimum number of moves the robot needs to
make to reach the destination. Output -1 if the destination is not
reachable. Assume that the blockade will never be at the starting
cell.



Input Format: First line contains the values of M and N matrix. Second
line contains the cell location of the robots starting position. Third
line contains the cell location of the destination. Fourth line and
the lines following that will contain the locations of the blockades.
The example below contains only one blockade at (2,2) where the robot
can't pass through. Below is the input:




3 3
1 1
3 3
2 2


Output should be 4 for above input.



Below is what I have started but confuse on how to deal with blockades here while doing BFS search:



  public static void main(String args ) throws Exception {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();

int startX = sc.nextInt();
int startY = sc.nextInt();

int destinationX = sc.nextInt();
int destinationY = sc.nextInt();

while (sc.hasNext()) {
int blockedX = sc.nextInt();
int blockedY = sc.nextInt();
}
}






java algorithm data-structures breadth-first-search dfs






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 20 '18 at 4:14







john

















asked Nov 20 '18 at 3:16









johnjohn

1,9521770156




1,9521770156













  • Note that you can also use depth first search for this.

    – vivek_23
    Nov 20 '18 at 6:26



















  • Note that you can also use depth first search for this.

    – vivek_23
    Nov 20 '18 at 6:26

















Note that you can also use depth first search for this.

– vivek_23
Nov 20 '18 at 6:26





Note that you can also use depth first search for this.

– vivek_23
Nov 20 '18 at 6:26












1 Answer
1






active

oldest

votes


















1














You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:



  1 2 3
1 • • •
2 • x •
3 • • •


we have the graph (using (row, col) notation):



(1,1) <-> (1,2)
(2,1) <-> (3,1)
(3,1) <-> (2,3)
(2,3) <-> (3,3)
(3,3) <-> (3,2)
(3,2) <-> (3,1)
(3,1) <-> (2,1)
(2,1) <-> (1,1)


where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:




  • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).

  • Initialize an empty queue of cells Q

  • Add the robot starting cell to Q

  • While Q is not empty:


    • Dequeue the next cell C from Q

    • For each non-blockade neighbor N of C (easy to determine from grid):


      • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.

      • If N is the destination cell, return N's distance.





  • At this point we know there's no path from the start cell to the destination cell.






share|improve this answer

























    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53385694%2ffind-the-shortest-path-to-reach-a-given-destination-cell-in-2d-matrix-with-obsta%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









    1














    You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:



      1 2 3
    1 • • •
    2 • x •
    3 • • •


    we have the graph (using (row, col) notation):



    (1,1) <-> (1,2)
    (2,1) <-> (3,1)
    (3,1) <-> (2,3)
    (2,3) <-> (3,3)
    (3,3) <-> (3,2)
    (3,2) <-> (3,1)
    (3,1) <-> (2,1)
    (2,1) <-> (1,1)


    where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:




    • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).

    • Initialize an empty queue of cells Q

    • Add the robot starting cell to Q

    • While Q is not empty:


      • Dequeue the next cell C from Q

      • For each non-blockade neighbor N of C (easy to determine from grid):


        • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.

        • If N is the destination cell, return N's distance.





    • At this point we know there's no path from the start cell to the destination cell.






    share|improve this answer






























      1














      You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:



        1 2 3
      1 • • •
      2 • x •
      3 • • •


      we have the graph (using (row, col) notation):



      (1,1) <-> (1,2)
      (2,1) <-> (3,1)
      (3,1) <-> (2,3)
      (2,3) <-> (3,3)
      (3,3) <-> (3,2)
      (3,2) <-> (3,1)
      (3,1) <-> (2,1)
      (2,1) <-> (1,1)


      where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:




      • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).

      • Initialize an empty queue of cells Q

      • Add the robot starting cell to Q

      • While Q is not empty:


        • Dequeue the next cell C from Q

        • For each non-blockade neighbor N of C (easy to determine from grid):


          • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.

          • If N is the destination cell, return N's distance.





      • At this point we know there's no path from the start cell to the destination cell.






      share|improve this answer




























        1












        1








        1







        You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:



          1 2 3
        1 • • •
        2 • x •
        3 • • •


        we have the graph (using (row, col) notation):



        (1,1) <-> (1,2)
        (2,1) <-> (3,1)
        (3,1) <-> (2,3)
        (2,3) <-> (3,3)
        (3,3) <-> (3,2)
        (3,2) <-> (3,1)
        (3,1) <-> (2,1)
        (2,1) <-> (1,1)


        where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:




        • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).

        • Initialize an empty queue of cells Q

        • Add the robot starting cell to Q

        • While Q is not empty:


          • Dequeue the next cell C from Q

          • For each non-blockade neighbor N of C (easy to determine from grid):


            • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.

            • If N is the destination cell, return N's distance.





        • At this point we know there's no path from the start cell to the destination cell.






        share|improve this answer















        You can simply view the grid as a graph: each cell is connected to its four neighbors (or fewer if it's on an edge), excluding any blockades. Using your example:



          1 2 3
        1 • • •
        2 • x •
        3 • • •


        we have the graph (using (row, col) notation):



        (1,1) <-> (1,2)
        (2,1) <-> (3,1)
        (3,1) <-> (2,3)
        (2,3) <-> (3,3)
        (3,3) <-> (3,2)
        (3,2) <-> (3,1)
        (3,1) <-> (2,1)
        (2,1) <-> (1,1)


        where all edge lengths are 1. Now you can apply a standard BFS from the start node until you reach the target node, keeping track of which nodes you visit. In pseudocode:




        • Mark all cell distances as infinite except for the robot starting cell, which has distance zero (you can do this using an extra 2D array, or maybe even in-place depending on how you store the grid).

        • Initialize an empty queue of cells Q

        • Add the robot starting cell to Q

        • While Q is not empty:


          • Dequeue the next cell C from Q

          • For each non-blockade neighbor N of C (easy to determine from grid):


            • If N's distance is infinity, mark N's distance to be (C's distance) + 1, and add N to Q.

            • If N is the destination cell, return N's distance.





        • At this point we know there's no path from the start cell to the destination cell.







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Nov 20 '18 at 4:29

























        answered Nov 20 '18 at 4:02









        arshajiiarshajii

        102k18183251




        102k18183251
































            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53385694%2ffind-the-shortest-path-to-reach-a-given-destination-cell-in-2d-matrix-with-obsta%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

            Guess what letter conforming each word

            Port of Spain

            Run scheduled task as local user group (not BUILTIN)