Source code for submission s850

Kon.java

  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. package kon;
  6.  
  7. import java.awt.Point;
  8. import java.util.LinkedList;
  9. import java.util.Queue;
  10. import java.util.Scanner;
  11.  
  12. /**
  13.  *
  14.  * @author student
  15.  */
  16. public class Kon {
  17.  
  18. private static boolean[][] map;
  19. private static int sx, sy, rx, ry, ex, ey;
  20. private static Queue<Point> st;
  21. private static int sol;
  22.  
  23. public static void main(String[] args) {
  24. Scanner sc = new Scanner(System.in);
  25.  
  26. int[][] podm = {{1,2},{2,1},{2, -1},{1,-2}, {-1,-2}, {-2,-1},{-2,1},{-1,2}};
  27.  
  28. while(sc.hasNextInt())
  29. {
  30. rx = sc.nextInt();
  31. ry = sc.nextInt();
  32. sx = sc.nextInt();
  33. sy = sc.nextInt();
  34. ex = sc.nextInt();
  35. ey = sc.nextInt();
  36.  
  37. st = new LinkedList<Point>();
  38.  
  39. map = new boolean[rx+1][ry+1];
  40. sol = 1;
  41.  
  42. map[sx][sy] = true;
  43. st.offer(new Point(sx, sy));
  44. st.offer(null);
  45.  
  46. while(true)
  47. {
  48. if(st.size() == 1)
  49. {
  50. System.out.println("impossible");
  51. break;
  52. }
  53. //System.out.println(st.size());
  54. Point p = st.remove();
  55.  
  56. if(p == null)
  57. {
  58. st.add(null);
  59. sol++;
  60. continue;
  61. }
  62.  
  63. int x, y;
  64. boolean mimo = false;
  65. for(int j=0; j<8; j++)
  66. {
  67. x = p.x + podm[j][0];
  68. y = p.y + podm[j][1];
  69.  
  70. if(0 < x && x <= rx && 0 < y && y <= ry)
  71. {
  72. mimo = solve(x, y);
  73. if(mimo) break;
  74. }
  75. }
  76. if(mimo) break;
  77.  
  78. /*if(p.x-2 > 0)
  79.   {
  80.   if(p.y+1 <= ry)
  81.   {
  82.   if(solve(p.x-2, p.y+1))
  83.   break;
  84.   }
  85.   else if(p.y-1 > 0)
  86.   {
  87.   if(solve(p.x-2, p.y-1))
  88.   break;
  89.   }
  90.   }
  91.   //atd
  92.  
  93.   if(p.x+1 <= rx)
  94.   {
  95.   if(p.y+2 <= ry)
  96.   {
  97.   if(solve(p.x+1, p.y+2))
  98.   break;
  99.   }
  100.   else if(p.y-2 > 0)
  101.   {
  102.   if(solve(p.x+1, p.y-2))
  103.   break;
  104.   }
  105.   }
  106.  
  107.   if(p.x+2 <= rx)
  108.   {
  109.   if(p.y+1 <= ry)
  110.   {
  111.   if(solve(p.x+2, p.y+1))
  112.   break;
  113.   }
  114.   else if(p.y-1 > 0)
  115.   {
  116.   if(solve(p.x+2, p.y-1))
  117.   break;
  118.   }
  119.   }
  120.  
  121.   //ds
  122.  
  123.   if(p.y-1 > 0)
  124.   {
  125.   if(p.x+2 <= rx)
  126.   {
  127.   if(solve(p.x+2, p.y-1))
  128.   break;
  129.   }
  130.   else if(p.x-2 > 0)
  131.   {
  132.   if(solve(p.x-2, p.y-1))
  133.   break;
  134.   }
  135.   }
  136.  
  137.   if(p.y-2 > 0)
  138.   {
  139.   if(p.x+1 <= rx)
  140.   {
  141.   if(solve(p.x+1, p.y-2))
  142.   break;
  143.   }
  144.   else if(p.x-1 > 0)
  145.   {
  146.   if(solve(p.x-1, p.y-2))
  147.   break;
  148.   }
  149.   }
  150.  
  151.   //
  152.  
  153.   if(p.y+1 <= ry)
  154.   {
  155.   if(p.x+2 <= rx)
  156.   {
  157.   if(solve(p.x+2, p.y+1))
  158.   break;
  159.   }
  160.   else if(p.x-2 > 0)
  161.   {
  162.   if(solve(p.x-2, p.y+1))
  163.   break;
  164.   }
  165.   }
  166.  
  167.   if(p.y+2 <= ry)
  168.   {
  169.   if(p.x+1 <= rx)
  170.   {
  171.   if(solve(p.x+1, p.y+2))
  172.   break;
  173.   }
  174.   else if(p.x-1 > 0)
  175.   {
  176.   if(solve(p.x-1, p.y+2))
  177.   break;
  178.   }
  179.   }*/
  180.  
  181. }
  182. }
  183. }
  184.  
  185. private static boolean solve(int x, int y)
  186. {
  187. if(!map[x][y])
  188. {
  189. if(x == ex && y == ey)
  190. {
  191. System.out.println(sol);
  192. return true;
  193. }
  194. else
  195. {
  196. st.offer(new Point(x, y));
  197. map[x][y] = true;
  198. }
  199. }
  200.  
  201. return false;
  202. }
  203. }
  204.