import java.util.Scanner;
public class A2Rcs {
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
System.out.println("\nEnter board size: ");
int size = input.nextInt();
int[][]board = new int[size][size];
for (int i = 0; i<size; i++) {
System.out.println("\nEnter the row: ");
for (int j = 0; j<size; j++) {
board[i][j] = input.nextInt();
}
}
System.out.println("\nData you entered: ");
for(int x = 0; x< size; x++){
for(int y = 0 ; y< size; y++){ 
System.out.print(board[x][y]);
} 
System.out.println(); 
}
System.out.println("\nEnter starting position: ");
int p1 = input.nextInt();
int p2 = input.nextInt();
if (magicBoard(p1, p2, board, size))
System.out.println("Solvable");		
}
public static Boolean magicBoard(int p1, int p2, int[][] board, int size) {
boolean result = false;
int temp;
while(!result) {
if(board[p1][p2] == 0) {
System.out.println("Reached 0.");
result = true;
break;
}           
//can only down
if((p1+board[p1][p2]) < size && (p1-board[p1][p2]) < 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)) {
temp = board[p1+board[p1][p2]][p2];
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
result = false;
break;
}
// If don't go back and forth, then we continue
else {
p1 = p1+board[p1][p2];
System.out.print("Move south " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
//can only up
else if((p1+board[p1][p2]) > size && (p1-board[p1][p2]) > 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)){
temp = board[p1-board[p1][p2]][p2];
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
result = false;
break;
}
else {
p1 = p1-board[p1][p2];
System.out.print("Move north " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
//can only up right
else if((p2+board[p1][p2])<size && (p2-board[p1][p2])<0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
temp = board[p1][p2+board[p1][p2]];
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
result = false;
break;
}
else {
p2 = p2+board[p1][p2];
System.out.print("Move east " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
//can only left
else if((p2+board[p1][p2]) > size && (p2-board[p1][p2])> 0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
temp = board[p1][p2-board[p1][p2]];
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
result = false; 
break;
}
else {
p2 = p2-board[p1][p2];
System.out.print("Move west " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
// can any direction
else {
// try moving south
SOUTH:
if(p1-board[p1][p2] < 0 && p1-board[p1][p2] > -size) {
temp = board[p1+board[p1][p2]][p2];
// Verify if we go back and forth if we go south, if we do, then we the result will be 
if(board[p1][p2] == temp) {
break SOUTH;
}
else {
p1 = p1+board[p1][p2];
System.out.print("Move south " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
NORTH: 
if(p1-board[p1][p2] > 0 && p1-board[p1][p2] < size) {
temp = board[p1-board[p1][p2]][p2];
if(board[p1][p2] == temp) {
break NORTH;
}
else {
p1 = p1-board[p1][p2];
System.out.print("Move north " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
// try moving east
EAST:
if(p2-board[p1][p2] < 0 ) {
temp = board[p1][p2+board[p1][p2]];
// If will go back and forth at that position, then we exit the EAST label and we go to the next label
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
break EAST;
}
else {
p2 = p2+board[p1][p2];
System.out.print("Move east " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
// Try moving west  
WEST:
if(p2-board[p1][p2] > 0) {
temp = board[p1][p2-board[p1][p2]];
// If we go back and forth in that position, then we exit the EAST label
if(board[p1][p2] == temp) {
System.out.print("The MagicBoard is unsolvable");
result = false;
break WEST;
}
else {
p2 = p2-board[p1][p2];
System.out.print("Move west " + board[p1][p2] + ", ");
magicBoard(p1, p2, board, size);
}
}
}
}
return result;
}
}

function backtrack(M, i, j, visited){
// Reached the goal!
if (M[i][j] == 0)
return true;
const d = M.length;
const move = M[i][j];
// Try visiting all directions
if (i + move < d && !visited[i + move][j]){
visited[i + move][j] = true;
if (backtrack(M, i + move, j, visited))
return true;
visited[i + move][j] = false;
}
if (i - move >= 0 && !visited[i - move][j]){
visited[i - move][j] = true;
if (backtrack(M, i - move, j, visited))
return true;
visited[i - move][j] = false;
}
if (j + move < d && !visited[i][j + move]){
visited[i][j + move] = true;
if (backtrack(M, i, j + move, visited))
return true;
visited[i][j + move] = false;
}
if (j - move >= 0 && !visited[i][j - move]){
visited[i][j - move] = true;
if (backtrack(M, i, j - move, visited))
return true;
visited[i][j - move] = false;
}
return false;
}
function f(M, start_i, start_j){
const d = M.length;
const visited = new Array(d);
for (let i=0; i<d; i++)
visited[i] = new Array(d).fill(false);
visited[start_i][start_j] = true;
return backtrack(M, start_i, start_j, visited);
}
var board_1 = [
[4, 2, 1, 3, 1],
[2, 3, 2, 1, 4],
[3, 2, 3, 1, 4],
[1, 3, 4, 2, 3],
[3, 3, 1, 2, 0]
];
var board_2 = [
[1, 4, 1, 3, 1],
[4, 3, 2, 1, 4],
[3, 2, 3, 1, 4],
[1, 3, 4, 2, 3],
[3, 4, 1, 2, 0]
];
console.log(f(board_1, 0, 0));
console.log(f(board_2, 0, 0));

function backtrack(M, i, j, visited){
// Reached the goal!
if (M[i][j] == 0)
return [[i,j]];
const d = M.length;
const move = M[i][j];
// Try visiting all directions
if (i + move < d && !visited[i + move][j]){
visited[i + move][j] = true;
const ms = backtrack(M, i + move, j, visited)
if (ms.length)
return [[i,j]].concat(ms);
visited[i + move][j] = false;
}
if (i - move >= 0 && !visited[i - move][j]){
visited[i - move][j] = true;
const ms = backtrack(M, i - move, j, visited)
if (ms.length)
return [[i,j]].concat(ms);
visited[i - move][j] = false;
}
if (j + move < d && !visited[i][j + move]){
visited[i][j + move] = true;
const ms = backtrack(M, i, j + move, visited)
if (ms.length)
return [[i,j]].concat(ms);
visited[i][j + move] = false;
}
if (j - move >= 0 && !visited[i][j - move]){
visited[i][j - move] = true;
const ms = backtrack(M, i, j - move, visited)
if (ms.length)
return [[i,j]].concat(ms);
visited[i][j - move] = false;
}
return [];
}
function f(M, start_i, start_j){
const d = M.length;
const visited = new Array(d);
for (let i=0; i<d; i++)
visited[i] = new Array(d).fill(false);
visited[start_i][start_j] = true;
return backtrack(M, start_i, start_j, visited);
}
var board_1 = [
[4, 2, 1, 3, 1],
[2, 3, 2, 1, 4],
[3, 2, 3, 1, 4],
[1, 3, 4, 2, 3],
[3, 3, 1, 2, 0]
];
var board_2 = [
[1, 4, 1, 3, 1],
[4, 3, 2, 1, 4],
[3, 2, 3, 1, 4],
[1, 3, 4, 2, 3],
[3, 4, 1, 2, 0]
];
console.log(JSON.stringify(f(board_1, 0, 0)));
console.log(JSON.stringify(f(board_2, 0, 0)));

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class A2Rcs {
private static int[][] board1 = {//test case 1
{4, 2, 1, 3, 1},
{2, 3, 2, 1, 4},
{3, 2, 3, 1, 4},
{1, 3, 4, 2, 3},
{3, 3, 1, 2, 0}
};
private static int[][] board2 = {//test case 2
{1, 4, 1, 3, 1},
{4, 3, 2, 1, 4},
{3, 2, 3, 1, 4},
{1, 3, 4, 2, 3},
{3, 4, 1, 2, 0}
};
private static boolean[][] visited; //mark visited nodes
//bfs uses queue. In this case each entry (List) in the queue represents an entire path.
//such path is represented by a list of row, column pairs
private static Queue<List<int[]>> queue;
public static void main(String[] args) {
magicBoard(0, 0, board1);
magicBoard(0, 0, board2);
}
public static Boolean magicBoard(int row, int col, int[][] board) {
List<int[]> path = new ArrayList<>(); //construct an empty path
path.add(new int[]{row,col}); //add starting point to the path
queue = new LinkedList<>(); //initialize queue
queue.add(path);//add path to queue
visited = new boolean[board.length][board[0].length]; //initialize visited
for (int i=0; i<visited.length ; i++){
for (int j=0; j<visited[0].length ; j++){
visited[i][j] = false;
}
}
visited[row][col] = true;//mark origin as visited
boolean result = magicBoardBFS(board); //run search
if (! result) {
System.out.println("\nPath not found.");
}
return result;
}
public static Boolean magicBoardBFS(int[][] board) {
List<int[]>path = queue.poll(); //pull head (first entered) entry from queue
if(path == null) return false;  //no more entries to process and target not found so return false
if(targetFound(board, path)) return true; //check if target reached
int[] rowColumnPair = path.get(path.size()-1); //last row, col pair in path
//get next reachable positions
List<int[]>neighbors = getNeighbors(board, rowColumnPair[0], rowColumnPair[1]);
//add neighbors to queue
for(int[] rowColPair : neighbors){
List<int[]>newPath = new ArrayList<>(path); //copy path
//and neighbor (next reachable position) to the path
newPath.add(rowColPair);
queue.add(newPath); //add new path to queue
}
return magicBoardBFS(board);
}
//check if last pair in path is the target
private static boolean targetFound(int[][] board,List<int[]>path ) {
int[] rowColPair = path.get(path.size()-1); //last row, col pair in path
int row = rowColPair[0], col = rowColPair[1];
if(board[row][col] == 0 ){//target found
System.out.println("Path found: ");
printPath(path);
return true;
}
return false;
}
private static List<int[]> getNeighbors(int[][] board, int row, int col) {
List<int[]>neighbors = new ArrayList<>();
int move = board[row][col];
//todo : assert that move is > 0
int[][] newRowColPairs = {{row + move, col},{row - move, col},  {row , col + move},{row , col - move} };
for(int[] rowColPair: newRowColPairs){
int newRow = rowColPair[0], newCol =rowColPair[1];
if(newRow < board.length && newRow >= 0
&& newCol < board[0].length && newCol >=0) { //valid row col
if(!visited[newRow][newCol]) { //unvisited
neighbors.add(new int[]{newRow, newCol});
visited[newRow][newCol] = true;
}
}
}
return neighbors;
}
private static void printPath(List<int[]> path) {
if(path == null) return;
for(int[] rowColPair : path){
System.out.print(Arrays.toString(rowColPair) +" ");
}
System.out.println();
}
}