YChalk

Minimum Knight Move

May 18th, 2022 (edited)
468
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.math.*;
  3. import java.security.*;
  4. import java.text.*;
  5. import java.util.*;
  6. import java.util.concurrent.*;
  7. import java.util.function.*;
  8. import java.util.regex.*;
  9. import java.util.stream.*;
  10. import static java.util.stream.Collectors.joining;
  11. import static java.util.stream.Collectors.toList;
  12.  
  13. class Result {
  14.  
  15.     /*
  16.      * Complete the 'knightlOnAChessboard' function below.
  17.      *
  18.      * The function is expected to return a 2D_INTEGER_ARRAY.
  19.      * The function accepts INTEGER n as parameter.
  20.      */
  21.  
  22.     public static List<List<Integer>> knightlOnAChessboard(int n) {
  23.     // Write your code here
  24.     List<List<Integer>> result = new ArrayList<>();
  25.     //int[][] grid = new int[n][n];
  26.     int[] start = new int[]{0,0};
  27.     List<int[]> next = new ArrayList<>();
  28.     next.add(start);
  29.    
  30.     for (int i = 1; i < n; i++) {
  31.         List<Integer> mins = new ArrayList<>();
  32.         for (int j = 1; j < n; j++) {
  33.             if (i == j) {
  34.                 if ((n-1) % i == 0) {
  35.                     mins.add((n-1) / i);
  36.                     continue;
  37.                 } else if (i > (n-1) / 2) {
  38.                     mins.add(-1);
  39.                     continue;
  40.                 }
  41.             }
  42.             if (i > j) {
  43.                 mins.add(result.get(j-1).get(i-1));
  44.                 continue;
  45.             }
  46.             mins.add(minimumMove(next, i, j, new int[n][n], n));
  47.         }
  48.         result.add(mins);
  49.     }
  50.    
  51.     //System.out.println(minimumMove(start, 1, 2, grid, n));
  52.  
  53.    
  54.     return result;
  55.  
  56.     }
  57.    
  58.     public static int minimumMove(List<int[]> start, int xMove, int yMove, int[][] grid, int n) {
  59.         int moves = 0;
  60.         List<int[]> next;
  61.         int subsequent;
  62.        
  63.         next = nextMove(start, xMove, yMove, grid, n);
  64.         if (next != null) {
  65.             moves++;
  66.             if (containsEnd(next, n)) {
  67.                 return moves;
  68.             }
  69.             subsequent = minimumMove(next, xMove, yMove, grid, n);
  70.             if (subsequent != -1) {
  71.                 return moves + subsequent;
  72.             }
  73.         }
  74.         return -1;                      
  75.     }
  76.    
  77.     public static List<int[]> nextMove(List<int[]> start, int xMove, int yMove, int[][] grid, int n) {
  78.         List<int[]> nextMove = new ArrayList<>();
  79.         int[] next;
  80.        
  81.         for (int[] pos : start) {
  82.             next = upRight(pos, xMove, yMove, grid, n);
  83.             if (next != null) {
  84.                 nextMove.add(next);
  85.             }
  86.             next = rightUp(pos, xMove, yMove, grid, n);
  87.             if (next != null) {
  88.                 nextMove.add(next);
  89.             }
  90.             next = rightDown(pos, xMove, yMove, grid, n);
  91.             if (next != null) {
  92.                 nextMove.add(next);
  93.             }
  94.             next = downRight(pos, xMove, yMove, grid, n);
  95.             if (next != null) {
  96.                 nextMove.add(next);
  97.             }
  98.             next = downLeft(pos, xMove, yMove, grid, n);
  99.             if (next != null) {
  100.                 nextMove.add(next);
  101.             }
  102.             next = leftDown(pos, xMove, yMove, grid, n);
  103.             if (next != null) {
  104.                 nextMove.add(next);
  105.             }
  106.             next = leftUp(pos, xMove, yMove, grid, n);
  107.             if (next != null) {
  108.                 nextMove.add(next);
  109.             }
  110.             next = upLeft(pos, xMove, yMove, grid, n);
  111.             if (next != null) {
  112.                 nextMove.add(next);
  113.             }
  114.         }
  115.        
  116.         return nextMove.size() > 0 ? nextMove : null;
  117.        
  118.     }
  119.    
  120.     public static boolean containsEnd(List<int[]> next, int n) {
  121.         for (int[] pos : next) {
  122.             if (end(pos, n)) {
  123.                 return true;
  124.             }
  125.         }
  126.         return false;
  127.     }
  128.    
  129.     public static boolean end(int[] next, int n) {
  130.         return next[0] == n-1 && next[1] == n-1;
  131.     }
  132.    
  133.     public static int[] upRight(int[] start, int xMove, int yMove, int[][] grid, int n) {
  134.         int xNew = start[0] - xMove;
  135.         int yNew = start[1] + yMove;
  136.        
  137.         if (xNew < 0 || yNew >= n) {
  138.             return null;
  139.         }
  140.        
  141.         if (grid[xNew][yNew] != 0) {
  142.             return null;
  143.         }
  144.        
  145.         grid[xNew][yNew] = 1;
  146.         return new int[]{xNew, yNew};
  147.     }
  148.    
  149.     public static int[] rightUp(int[] start, int xMove, int yMove, int[][] grid, int n) {
  150.         int xNew = start[0] - yMove;
  151.         int yNew = start[1] + xMove;
  152.        
  153.         if (xNew < 0 || yNew >= n) {
  154.             return null;
  155.         }
  156.        
  157.         if (grid[xNew][yNew] != 0) {
  158.             return null;
  159.         }
  160.        
  161.         grid[xNew][yNew] = 1;
  162.         return new int[]{xNew, yNew};
  163.     }
  164.    
  165.     public static int[] rightDown(int[] start, int xMove, int yMove, int[][] grid, int n) {
  166.         int xNew = start[0] + yMove;
  167.         int yNew = start[1] + xMove;
  168.        
  169.         if (xNew >= n || yNew >= n) {
  170.             return null;
  171.         }
  172.        
  173.         if (grid[xNew][yNew] != 0) {
  174.             return null;
  175.         }
  176.        
  177.         grid[xNew][yNew] = 1;
  178.         return new int[]{xNew, yNew};
  179.     }
  180.    
  181.     public static int[] downRight(int[] start, int xMove, int yMove, int[][] grid, int n) {
  182.         int xNew = start[0] + xMove;
  183.         int yNew = start[1] + yMove;
  184.        
  185.         if (xNew >= n || yNew >= n) {
  186.             return null;
  187.         }
  188.        
  189.         if (grid[xNew][yNew] != 0) {
  190.             return null;
  191.         }
  192.        
  193.         grid[xNew][yNew] = 1;
  194.         return new int[]{xNew, yNew};
  195.     }
  196.    
  197.     public static int[] downLeft(int[] start, int xMove, int yMove, int[][] grid, int n) {
  198.         int xNew = start[0] + xMove;
  199.         int yNew = start[1] - yMove;
  200.        
  201.         if (yNew < 0 || xNew >= n) {
  202.             return null;
  203.         }
  204.        
  205.         if (grid[xNew][yNew] != 0) {
  206.             return null;
  207.         }
  208.        
  209.         grid[xNew][yNew] = 1;
  210.         return new int[]{xNew, yNew};
  211.     }
  212.    
  213.     public static int[] leftDown(int[] start, int xMove, int yMove, int[][] grid, int n) {
  214.         int xNew = start[0] + yMove;
  215.         int yNew = start[1] - xMove;
  216.        
  217.         if (yNew < 0 || xNew >= n) {
  218.             return null;
  219.         }
  220.        
  221.         if (grid[xNew][yNew] != 0) {
  222.             return null;
  223.         }
  224.        
  225.         grid[xNew][yNew] = 1;
  226.         return new int[]{xNew, yNew};
  227.     }
  228.    
  229.     public static int[] leftUp(int[] start, int xMove, int yMove, int[][] grid, int n) {
  230.         int xNew = start[0] - yMove;
  231.         int yNew = start[1] - xMove;
  232.        
  233.         if (xNew < 0 || yNew < 0) {
  234.             return null;
  235.         }
  236.        
  237.         if (grid[xNew][yNew] != 0) {
  238.             return null;
  239.         }
  240.        
  241.         grid[xNew][yNew] = 1;
  242.         return new int[]{xNew, yNew};
  243.     }
  244.    
  245.     public static int[] upLeft(int[] start, int xMove, int yMove, int[][] grid, int n) {
  246.         int xNew = start[0] - xMove;
  247.         int yNew = start[1] - yMove;
  248.        
  249.         if (xNew < 0 || yNew < 0) {
  250.             return null;
  251.         }
  252.        
  253.         if (grid[xNew][yNew] != 0) {
  254.             return null;
  255.         }
  256.        
  257.         grid[xNew][yNew] = 1;
  258.         return new int[]{xNew, yNew};
  259.     }
  260.  
  261. }
  262.  
  263. public class Solution {
  264.     public static void main(String[] args) throws IOException {
  265.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  266.         BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  267.  
  268.         int n = Integer.parseInt(bufferedReader.readLine().trim());
  269.  
  270.         List<List<Integer>> result = Result.knightlOnAChessboard(n);
  271.  
  272.         result.stream()
  273.             .map(
  274.                 r -> r.stream()
  275.                     .map(Object::toString)
  276.                     .collect(joining(" "))
  277.             )
  278.             .map(r -> r + "\n")
  279.             .collect(toList())
  280.             .forEach(e -> {
  281.                 try {
  282.                     bufferedWriter.write(e);
  283.                 } catch (IOException ex) {
  284.                     throw new RuntimeException(ex);
  285.                 }
  286.             });
  287.  
  288.         bufferedReader.close();
  289.         bufferedWriter.close();
  290.     }
  291. }
  292.  
RAW Paste Data Copied