Path finding given 2D array, Java

Path finding given 2D array

/**
 *  Find if a path exists from top left corner of given 2D array map, considering
 *  1 as path and 0 as walls, to the position where 'X' is placed.
 *
 *  This program uses Breadth-First search, and marks current position as '0' to mark
 *  it as visited point.
 *
 *  @author: Jayesh Chandrapal
 */

import java.util.*;
import java.lang.*;

class Node {
    int x;
    int y;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Rextester
{  
    public static void main(String args[])
    {
        char[][] matrix = {
            {'1', '0', '1', '1'},
            {'1', '1', '1', '1'},
            {'1', '1', '1', '1'},
            {'1', '1', '1', 'X'}
        };
        
        boolean pathExists = pathExists(matrix);
        
        System.out.println(pathExists ? "YES" : "NO");
    }
    
    public static boolean pathExists(char[][] matrix) {
        int N = matrix.length;
        
        List<Node> queue = new ArrayList<Node>();
        queue.add(new Node(0, 0));
        boolean pathExists = false;
        
        while(!queue.isEmpty()) {
            Node current = queue.remove(0);
            if(matrix[current.x][current.y] == 'X') {
                pathExists = true;
                break;
            }
            
            matrix[current.x][current.y] = '0'; // mark as visited
            
            List<Node> neighbors = getNeighbors(matrix, current);
            queue.addAll(neighbors);
        }
        
        return pathExists;
    }
    
    public static List<Node> getNeighbors(char[][] matrix, Node node) {
        List<Node> neighbors = new ArrayList<Node>();
        
        if(isValidPoint(matrix, node.x - 1, node.y)) {
            neighbors.add(new Node(node.x - 1, node.y));
        }
        
        if(isValidPoint(matrix, node.x + 1, node.y)) {
            neighbors.add(new Node(node.x + 1, node.y));
        }
        
        if(isValidPoint(matrix, node.x, node.y - 1)) {
            neighbors.add(new Node(node.x, node.y - 1));
        }
        
        if(isValidPoint(matrix, node.x, node.y + 1)) {
            neighbors.add(new Node(node.x, node.y + 1));
        }
        
        return neighbors;
    }
    
    public static boolean isValidPoint(char[][] matrix, int x, int y) {
        return !(x < 0 || x >= matrix.length || y < 0 || y >= matrix.length) && (matrix[x][y] != '0');
    }
}


run \| edit \| history \| help	0

Can you please show the solution if the start is everywhere on a first line, where "1" is; the finish point is also anywhere, where "1" on a bottom line is. the binary matrix size itself can be customized by user input. The search can go only right, left and down. Here is my code for the matrix: `public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    System.out.print("Enter size of the cheese: ");

    int matrix_size = in.nextInt();
    Random r = new Random();
    int[][] cheese = new int[matrix_size][matrix_size];
    for (int i = 0; i < matrix_size; i++) {
        for (int j = 0; j < matrix_size; j++) {
           cheese [i][j] = r.nextInt(2);
            System.out.print(cheese[i][j] + "\t");
        }
        System.out.print("\n");

    }`

by Nele, 2 years ago

Please log in to post a comment.