fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4. 	private static int[][] KNIGHT_MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
  5.  
  6. 	private static boolean[][] cleanBoard() {
  7. 		boolean [][] board = new boolean[8][];
  8. 		for (int i = 0; i < 8; ++i) {
  9. 			board[i] = new boolean[8];
  10. 		}
  11. 		return board;
  12. 	}
  13.  
  14. 	private static boolean isValidCoordinates(int x, int y) {
  15. 		return ((0 <= x && x < 8) && (0 <= y && y < 8));
  16. 	}
  17.  
  18. 	private static void safeSet(boolean[][] board, int x, int y, boolean value) {
  19. 		if (isValidCoordinates(x, y)) {
  20. 			board[x][y] = value;
  21. 		}
  22. 	}
  23.  
  24. 	//kinda Lee algorithm
  25. 	private static boolean[][] nextKnightMove(boolean[][] currentBoard) {
  26. 		boolean[][] result = cleanBoard();
  27. 		for (int x = 0; x < 8; ++x) {
  28. 			for (int y = 0; y < 8; ++y) {
  29. 				if (currentBoard[x][y]) {
  30. 					for (int[] move : KNIGHT_MOVES) {
  31. 						int newX = x + move[0];
  32. 						int newY = y + move[1];
  33.  
  34. 						safeSet(result, newX, newY, true);
  35. 					}
  36. 				}
  37. 			}
  38.  
  39. 		}
  40. 		return result;
  41. 	}
  42.  
  43. 	public static float solve(boolean[][] reachableByKnight, Point2d pawn) {
  44. 		float result = 1;
  45.  
  46. 		//check if pawn may already be taken
  47. 		if (reachableByKnight[pawn.x][pawn.y]) {
  48. 			result = -1;
  49. 		}
  50. 		else {
  51. 			while (pawn.y < 8 - 1) { // we start with white's move
  52. 				// knight may blocks
  53. 				if (reachableByKnight[pawn.x][pawn.y + 1]) {
  54. 					result = 0.5f;
  55. 					//We can't win after draw. No need to consider this square anymore.
  56. 					reachableByKnight[pawn.x][pawn.y + 1] = false;
  57. 				}
  58.  
  59. 				// pawn may take, so there are forbidden squares for knight
  60. 				safeSet(reachableByKnight, pawn.x - 1, pawn.y + 1, false);
  61. 				safeSet(reachableByKnight, pawn.x + 1, pawn.y + 1, false);
  62.  
  63. 				// otherwise white move forward
  64. 				++pawn.y;
  65.  
  66. 				// and knight makes next move
  67. 				reachableByKnight = nextKnightMove(reachableByKnight);
  68.  
  69. 				// if knight can take pawn then black immediately win
  70. 				if (reachableByKnight[pawn.x][pawn.y]) {
  71. 					result = -1;
  72. 					break;
  73. 				}
  74. 			}
  75. 		}
  76.  
  77. 		return result;
  78. 	}
  79.  
  80. 	//btw, if knight and pawn are on different colored squares then knight can't win - every move color of squares under knight and pawn changes
  81. 	public static float solve(Point2d pawn, Point2d knight) {
  82. 		boolean[][] reachableByKnight = cleanBoard();
  83.  
  84. 		reachableByKnight[knight.x][knight.y] = true;
  85.  
  86. 		float resultCase2 = -1;
  87. 		// consider case when pawn makes 2-square move in the beginning
  88. 	    if (pawn.y == 1) {
  89. 	        boolean isColliding = (knight.x == pawn.x) && (knight.y == 2 || knight.y == 3);
  90. 	        if (!isColliding) {
  91. 	            Point2d pawnCase2 = new Point2d(pawn);
  92. 	            pawnCase2.y += 2;
  93. 	            boolean[][] reachableByKnightCase2 = nextKnightMove(reachableByKnight);
  94. 	            resultCase2 = solve(reachableByKnightCase2, pawnCase2);
  95. 	        }
  96. 	    }
  97.  
  98. 		// case without 2-square move by pawn
  99. 		float resultCase1 = solve(reachableByKnight, pawn);
  100. 		return Math.max(resultCase1, resultCase2);
  101. 	}
  102.  
  103. 	public static void main(String[] args) {
  104. 		Scanner in = new Scanner(System.in);
  105. 		Point2d pawn = new Point2d(in.next());
  106. 		Point2d knight = new Point2d(in.next());
  107. 		in.close();
  108.  
  109. 		System.out.println(solve(pawn, knight));
  110. 	}
  111.  
  112.  
  113. 	public static class Point2d {
  114. 		public int x = 0;
  115. 		public int y = 0;
  116.  
  117. 		public Point2d() {}
  118.  
  119. 		public Point2d(Point2d other) {
  120. 			this.x = other.x;
  121. 			this.y = other.y;
  122. 		}
  123.  
  124. 		public Point2d(String s) {
  125. 			assert s.matches("[a-h][1-8]");
  126. 			this.x = s.charAt(0) - 'a';
  127. 			this.y = s.charAt(1) - '1';
  128. 		}
  129. 	}
  130. }
Success #stdin #stdout 0.16s 321344KB
comments (?)
stdin
copy 
a1 b2
stdout
copy 
1.0
https://ideone.com/V5zFoc
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!