import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Node { int x; int y; Node(int x, int y) { this.x = x; this.y = y; } } public class Solution { static HashMap memo = new HashMap(); static int arraySize; static int KnightL(int a,int b,int n) { String key = b+"-"+a; if(memo.containsKey(key)) { return memo.get(key); } int[][] distances = new int[n][n]; LinkedList queue = new LinkedList(); queue.add(new Node(0,0)); while(!queue.isEmpty()) { Node currentNode = queue.pop(); if(currentNode.x == n-1 && currentNode.y == n-1) { key=a+"-"+b; int distValue = distances[currentNode.x][currentNode.y]; memo.put(key,distValue); return distValue; } ArrayList possibleMoves = getAdjacentNodes(currentNode,a,b,distances); for(Node node:possibleMoves) { distances[node.x][node.y] = distances[currentNode.x][currentNode.y] + 1; queue.add(node); } } return -1; } static ArrayList getAdjacentNodes(Node node,int a,int b,int[][] distances) { int x = node.x; int y = node.y; ArrayList nodes = new ArrayList(); if(islegal(x-a,y-b)&& distances[x-a][y-b] == 0) { nodes.add(new Node(x-a,y-b)); } if(islegal(x-b,y-a) && distances[x-b][y-a] == 0) { nodes.add(new Node(x-b,y-a)); } if(islegal(x+a,y+b) && distances[x+a][y+b] == 0) { nodes.add(new Node(x+a,y+b)); } if(islegal(x+b,y+a) && distances[x+b][y+a] == 0) { nodes.add(new Node(x+b,y+a)); } if(islegal(x-a,y+b) && distances[x-a][y+b] == 0) { nodes.add(new Node(x-a,y+b)); } if(islegal(x+a,y-b) && distances[x+a][y-b] == 0) { nodes.add(new Node(x+a,y-b)); } if(islegal(x+b,y-a) && distances[x+b][y-a] == 0) { nodes.add(new Node(x+b,y-a)); } if(islegal(x-b,y+a) && distances[x-b][y+a] == 0) { nodes.add(new Node(x-b,y+a)); } return nodes; } static void findPossiblePathsFromStoT(int n) { for(int a=1;a=0 && x=0 && y