Given a 2-D Matrix find path from starting cell to Goal cell, a bot can move in 8 directions (North, North east, east , south east, south, south west, west, north west). if cell value =0 implies block and if cell Value =1 implies Path exist.

/*
start : (row = 1, col = 3)
Goal  : (row = 6, col = 3)
   
            c1  c2 c3  c4  c5
    row1    0   0   1   0   0
    row2    0   0   0   1   0
    row3    0   1   1   0   0
    row4    0   1   0   0   0
    row5    0   0   1   0   0
    row6    0   0   1   0   0
    row7    1   0   0   0   0
       
Path:
    Start(r1 c3) -> (r2 c4) -> (r3 c3) -> (r4 c2) -> (r5 c3) -> (r6 c3) Goal

Below is the java code.

*/

public class Solution {
    private int[][] moves = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
    private int[][] maze = {{0,0,1,0,0},{0,0,0,1,0},{0,1,1,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,1,0,0},{1,0,0,0,0}};
    private int[][] sol = maze.clone();
    private int mazeWidth = maze[0].length;
    private int mazeHeight = maze.length;
    private int xStart = 0;
    private int yStart = 2;
    private int xGoal = 5;
    private int yGoal = 2;
    private boolean result = false;
   
    public void startBot()
    {
        sol[xStart][yStart] = 2;
        result = moveToGoal(xStart,yStart);
        displayResult();
    }
   
    public boolean movePossible(int r, int c)
    {
        if(r <0 || r>= mazeHeight || c >= mazeWidth || c<0)
        {
            return false;
        }
       
        if(sol[r][c] ==1)
        {
            return true;
        }
        return false;
    }
   
    public void makeMove(int r, int c)
    {
        sol[r][c] = 2;
    }
   
    public void unmakeMove(int r , int c)
    {
        sol[r][c] = 1;
    }
   
    public boolean moveToGoal(int x , int y)
    {
        if(x == xGoal && y == yGoal)
        {
            return true;
        }
       
        for(int i =0 ; i<moves.length; i++)
        {
            if(movePossible(x+moves[i][0], y+moves[i][1]))
            {
                makeMove(x+moves[i][0] , y+moves[i][1]);
                if( moveToGoal(x+moves[i][0], y+moves[i][1]) )
                {
                    return true;
                }
                unmakeMove(x+moves[i][0], y+moves[i][1]);
            }
        }
        return false;
    }
   
    public void displayResult()
    {
        if(result)
        {
            System.out.println("SOLUTION FOUND");
       
            for(int i =0 ; i<mazeHeight; i++)
            {
                for(int j =0 ; j<mazeWidth; j++)
                {
                    if(sol[i][j] ==2)
                    {
                        System.out.println("xpos : " + i + "   ypos : " + j);
                    }
                }
            }
        }
        else
        {
            System.out.println("NO SOLUTION");
        }
    }
   
    public static void main(String args[])
    {
        Solution s = new Solution();
        s.startBot();
    }
   
}