API tools faq
paste
Advertisement
Xenithz

Knight Problem ACM-ICPC [Hard code]

Xenithz
Aug 5th, 2011
117
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 23.40 KB | None | 0 0
raw download clone embed print report
  1. package problemsolve;
  2.  
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6.  
  7. public class Knight2 {
  8.    public static Integer checkDirection(Integer CurrentX, Integer CurrentY,Integer targetX,Integer targetY) {
  9.         if(CurrentX == targetX && CurrentY == targetY){
  10.             return 0;
  11.         }
  12.         else if (CurrentX < targetX && CurrentY != targetY) {
  13.             if (CurrentY < targetY) {
  14.                 return 1; // goto Right up Node (x+1,y+2) , (x+2,y+1)
  15.             } else {
  16.                 return 2; // goto Right Down Node (x+1,y-2) , (x+2,y-1)
  17.             }
  18.         } else if (CurrentX == targetX) {
  19.             if (CurrentY < targetY) {
  20.                 return 3; // go up Right and Left Node (x+1,y+2) , (x+2,y+1) , (x-1,y+2) , (x-2,y+1)
  21.             } else {
  22.                 return 4; // go down Right and left Node (x+1,y-2) , (x+2,y-1) , (x-2,y-1) , (x-1,y-2)
  23.             }
  24.         } else if (CurrentX > targetX && CurrentY != targetY) {
  25.             if (CurrentY < targetY) {
  26.                 return 5; // goto Left up Node (x-1,y+2) , (x-2,y+1)
  27.             } else {
  28.                 return 6; // goto Left Down Node (x-2,y-1) , (x-1,y-2)
  29.             }
  30.         } else if (CurrentY == targetY) {
  31.             if (CurrentX < targetX) {
  32.                 return 7; // goto Right up&down Node (x+1,y+2) , (x+2,y+1) , (x+1,y-2) , (x+2,y-1)
  33.             } else {
  34.                 return 8; // goto Left up&down Node (x-1,y+2) , (x-2,y+1) , (x-2,y-1) , (x-1,y-2)
  35.             }
  36.         }
  37.         return 0;
  38.     }
  39.  
  40.     static void BFS(int startX, int startY, chessNode[][] chessPanel, int size,int tx,int ty) {
  41.         LinkedList queue = new LinkedList();
  42.         chessNode Currentnode = null, nextNode = null;
  43.         Currentnode = new chessNode(startX, startY, false, 0, false);     // Create Start Node
  44.         queue.addLast(Currentnode);
  45.         int step = 0;
  46.         while (!queue.isEmpty()) {  // no out if not Found
  47.             Currentnode = (chessNode) queue.removeFirst();                      // Remove From Queue To Check
  48.             if (Currentnode.isTarget()) {                                         // w00t!! w00t!! Found
  49.                 System.out.println();
  50.                 break;
  51.             }
  52.             int direction = checkDirection(Currentnode.getX(), Currentnode.getY(), tx, ty);
  53.             switch (direction) {
  54.             case 1:                                                                
  55.                 int x = Currentnode.getX() + 2;
  56.                 int y = Currentnode.getY() + 1;
  57.                 step = Currentnode.getStep();                                          
  58.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  59.                     if (chessPanel[x][y] == null) {                                  
  60.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  61.                     }
  62.                     nextNode = chessPanel[x][y];
  63.                     if (!nextNode.isVisited()) {                                  
  64.                         nextNode.setVisited(true);                                
  65.                         nextNode.setStep(step + 1);                          
  66.                         queue.addLast(nextNode);                                
  67.                     }
  68.                 }
  69.                 x = Currentnode.getX() + 1;
  70.                 y = Currentnode.getY() + 2;
  71.                 step = Currentnode.getStep();                                  
  72.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  73.                     if (chessPanel[x][y] == null) {                                  
  74.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  75.                     }
  76.                     nextNode = chessPanel[x][y];
  77.                     if (!nextNode.isVisited()) {                                  
  78.                         nextNode.setVisited(true);                  
  79.                         nextNode.setStep(step + 1);
  80.                         queue.addLast(nextNode);  
  81.                     }
  82.                 }
  83.  
  84.                 break;
  85.             case 2:
  86.                  x = Currentnode.getX() + 2;
  87.                  y = Currentnode.getY() - 1;
  88.                 step = Currentnode.getStep();                                          
  89.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  90.                     if (chessPanel[x][y] == null) {                                  
  91.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  92.                     }
  93.                     nextNode = chessPanel[x][y];
  94.                     if (!nextNode.isVisited()) {                                  
  95.                         nextNode.setVisited(true);                                
  96.                         nextNode.setStep(step + 1);                          
  97.                         queue.addLast(nextNode);                                
  98.                     }
  99.                 }
  100.                 x = Currentnode.getX() + 1;
  101.                 y = Currentnode.getY() - 2;
  102.                 step = Currentnode.getStep();                                  
  103.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  104.                     if (chessPanel[x][y] == null) {                                  
  105.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  106.                     }
  107.                     nextNode = chessPanel[x][y];
  108.                     if (!nextNode.isVisited()) {                                  
  109.                         nextNode.setVisited(true);                  
  110.                         nextNode.setStep(step + 1);
  111.                         queue.addLast(nextNode);  
  112.                     }
  113.                 }
  114.                 break;
  115.             case 3:
  116.                  x = Currentnode.getX() - 2;
  117.                  y = Currentnode.getY() + 1;
  118.                 step = Currentnode.getStep();                                          
  119.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  120.                     if (chessPanel[x][y] == null) {                                  
  121.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  122.                     }
  123.                     nextNode = chessPanel[x][y];
  124.                     if (!nextNode.isVisited()) {                                  
  125.                         nextNode.setVisited(true);                                
  126.                         nextNode.setStep(step + 1);                          
  127.                         queue.addLast(nextNode);                                
  128.                     }
  129.                 }
  130.                 x = Currentnode.getX() - 1;
  131.                 y = Currentnode.getY() + 2;
  132.                 step = Currentnode.getStep();                                  
  133.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  134.                     if (chessPanel[x][y] == null) {                                  
  135.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  136.                     }
  137.                     nextNode = chessPanel[x][y];
  138.                     if (!nextNode.isVisited()) {                                  
  139.                         nextNode.setVisited(true);                  
  140.                         nextNode.setStep(step + 1);
  141.                         queue.addLast(nextNode);  
  142.                     }
  143.                 }
  144.                  x = Currentnode.getX() + 2;
  145.                  y = Currentnode.getY() + 1;
  146.                 step = Currentnode.getStep();                                          
  147.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  148.                     if (chessPanel[x][y] == null) {                                  
  149.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  150.                     }
  151.                     nextNode = chessPanel[x][y];
  152.                     if (!nextNode.isVisited()) {                                  
  153.                         nextNode.setVisited(true);                                
  154.                         nextNode.setStep(step + 1);                          
  155.                         queue.addLast(nextNode);                                
  156.                     }
  157.                 }
  158.                 x = Currentnode.getX() + 1;
  159.                 y = Currentnode.getY() + 2;
  160.                 step = Currentnode.getStep();                                  
  161.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  162.                     if (chessPanel[x][y] == null) {                                  
  163.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  164.                     }
  165.                     nextNode = chessPanel[x][y];
  166.                     if (!nextNode.isVisited()) {                                  
  167.                         nextNode.setVisited(true);                  
  168.                         nextNode.setStep(step + 1);
  169.                         queue.addLast(nextNode);  
  170.                     }
  171.                 }
  172.  
  173.                 break;
  174.             case 4:
  175.                  x = Currentnode.getX() - 1;
  176.                  y = Currentnode.getY() - 2;
  177.                 step = Currentnode.getStep();                                          
  178.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  179.                     if (chessPanel[x][y] == null) {                                  
  180.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  181.                     }
  182.                     nextNode = chessPanel[x][y];
  183.                     if (!nextNode.isVisited()) {                                  
  184.                         nextNode.setVisited(true);                                
  185.                         nextNode.setStep(step + 1);                          
  186.                         queue.addLast(nextNode);                                
  187.                     }
  188.                 }
  189.                 x = Currentnode.getX() - 1;
  190.                 y = Currentnode.getY() - 2;
  191.                 step = Currentnode.getStep();                                  
  192.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  193.                     if (chessPanel[x][y] == null) {                                  
  194.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  195.                     }
  196.                     nextNode = chessPanel[x][y];
  197.                     if (!nextNode.isVisited()) {                                  
  198.                         nextNode.setVisited(true);                  
  199.                         nextNode.setStep(step + 1);
  200.                         queue.addLast(nextNode);  
  201.                     }
  202.                 }
  203.                  x = Currentnode.getX() + 2;
  204.                  y = Currentnode.getY() - 1;
  205.                 step = Currentnode.getStep();                                          
  206.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  207.                     if (chessPanel[x][y] == null) {                                  
  208.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  209.                     }
  210.                     nextNode = chessPanel[x][y];
  211.                     if (!nextNode.isVisited()) {                                  
  212.                         nextNode.setVisited(true);                                
  213.                         nextNode.setStep(step + 1);                          
  214.                         queue.addLast(nextNode);                                
  215.                     }
  216.                 }
  217.                 x = Currentnode.getX() + 1;
  218.                 y = Currentnode.getY() - 2;
  219.                 step = Currentnode.getStep();                                  
  220.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  221.                     if (chessPanel[x][y] == null) {                                  
  222.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  223.                     }
  224.                     nextNode = chessPanel[x][y];
  225.                     if (!nextNode.isVisited()) {                                  
  226.                         nextNode.setVisited(true);                  
  227.                         nextNode.setStep(step + 1);
  228.                         queue.addLast(nextNode);  
  229.                     }
  230.                 }
  231.                 break;
  232.             case 5:
  233.                  x = Currentnode.getX() - 2;
  234.                  y = Currentnode.getY() + 1;
  235.                 step = Currentnode.getStep();                                          
  236.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  237.                     if (chessPanel[x][y] == null) {                                  
  238.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  239.                     }
  240.                     nextNode = chessPanel[x][y];
  241.                     if (!nextNode.isVisited()) {                                  
  242.                         nextNode.setVisited(true);                                
  243.                         nextNode.setStep(step + 1);                          
  244.                         queue.addLast(nextNode);                                
  245.                     }
  246.                 }
  247.                 x = Currentnode.getX() - 1;
  248.                 y = Currentnode.getY() + 2;
  249.                 step = Currentnode.getStep();                                  
  250.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  251.                     if (chessPanel[x][y] == null) {                                  
  252.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  253.                     }
  254.                     nextNode = chessPanel[x][y];
  255.                     if (!nextNode.isVisited()) {                                  
  256.                         nextNode.setVisited(true);                  
  257.                         nextNode.setStep(step + 1);
  258.                         queue.addLast(nextNode);  
  259.                     }
  260.                 }
  261.                 break;
  262.             case 6:
  263.                  x = Currentnode.getX() - 2;
  264.                  y = Currentnode.getY() - 1;
  265.                 step = Currentnode.getStep();                                          
  266.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  267.                     if (chessPanel[x][y] == null) {                                  
  268.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  269.                     }
  270.                     nextNode = chessPanel[x][y];
  271.                     if (!nextNode.isVisited()) {                                  
  272.                         nextNode.setVisited(true);                                
  273.                         nextNode.setStep(step + 1);                          
  274.                         queue.addLast(nextNode);                                
  275.                     }
  276.                 }
  277.                 x = Currentnode.getX() - 1;
  278.                 y = Currentnode.getY() - 2;
  279.                 step = Currentnode.getStep();                                  
  280.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  281.                     if (chessPanel[x][y] == null) {                                  
  282.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  283.                     }
  284.                     nextNode = chessPanel[x][y];
  285.                     if (!nextNode.isVisited()) {                                  
  286.                         nextNode.setVisited(true);                  
  287.                         nextNode.setStep(step + 1);
  288.                         queue.addLast(nextNode);  
  289.                     }
  290.                 }
  291.                 break;
  292.             case 7:
  293.  
  294.                  x = Currentnode.getX() + 2;
  295.                  y = Currentnode.getY() - 1;
  296.                 step = Currentnode.getStep();                                          
  297.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  298.                     if (chessPanel[x][y] == null) {                                  
  299.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  300.                     }
  301.                     nextNode = chessPanel[x][y];
  302.                     if (!nextNode.isVisited()) {                                  
  303.                         nextNode.setVisited(true);                                
  304.                         nextNode.setStep(step + 1);                          
  305.                         queue.addLast(nextNode);                                
  306.                     }
  307.                 }
  308.                 x = Currentnode.getX() + 1;
  309.                 y = Currentnode.getY() - 2;
  310.                 step = Currentnode.getStep();                                  
  311.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  312.                     if (chessPanel[x][y] == null) {                                  
  313.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  314.                     }
  315.                     nextNode = chessPanel[x][y];
  316.                     if (!nextNode.isVisited()) {                                  
  317.                         nextNode.setVisited(true);                  
  318.                         nextNode.setStep(step + 1);
  319.                         queue.addLast(nextNode);  
  320.                     }
  321.                 }
  322.                  x = Currentnode.getX() + 2;
  323.                  y = Currentnode.getY() + 1;
  324.                 step = Currentnode.getStep();                                          
  325.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  326.                     if (chessPanel[x][y] == null) {                                  
  327.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  328.                     }
  329.                     nextNode = chessPanel[x][y];
  330.                     if (!nextNode.isVisited()) {                                  
  331.                         nextNode.setVisited(true);                                
  332.                         nextNode.setStep(step + 1);                          
  333.                         queue.addLast(nextNode);                                
  334.                     }
  335.                 }
  336.                 x = Currentnode.getX() + 1;
  337.                 y = Currentnode.getY() + 2;
  338.                 step = Currentnode.getStep();                                  
  339.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  340.                     if (chessPanel[x][y] == null) {                                  
  341.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  342.                     }
  343.                     nextNode = chessPanel[x][y];
  344.                     if (!nextNode.isVisited()) {                                  
  345.                         nextNode.setVisited(true);                  
  346.                         nextNode.setStep(step + 1);
  347.                         queue.addLast(nextNode);  
  348.                     }
  349.                 }
  350.                 break;
  351.             case 8:
  352.                  x = Currentnode.getX() + 2;
  353.                  y = Currentnode.getY() - 1;
  354.                 step = Currentnode.getStep();                                          
  355.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  356.                     if (chessPanel[x][y] == null) {                                  
  357.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  358.                     }
  359.                     nextNode = chessPanel[x][y];
  360.                     if (!nextNode.isVisited()) {                                  
  361.                         nextNode.setVisited(true);                                
  362.                         nextNode.setStep(step + 1);                          
  363.                         queue.addLast(nextNode);                                
  364.                     }
  365.                 }
  366.                 x = Currentnode.getX() - 1;
  367.                 y = Currentnode.getY() - 2;
  368.                 step = Currentnode.getStep();                                  
  369.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  370.                     if (chessPanel[x][y] == null) {                                  
  371.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  372.                     }
  373.                     nextNode = chessPanel[x][y];
  374.                     if (!nextNode.isVisited()) {                                  
  375.                         nextNode.setVisited(true);                  
  376.                         nextNode.setStep(step + 1);
  377.                         queue.addLast(nextNode);  
  378.                     }
  379.                 }
  380.                  x = Currentnode.getX() - 2;
  381.                  y = Currentnode.getY() + 1;
  382.                 step = Currentnode.getStep();                                          
  383.                 if (x >= 0 && x < size && y >= 0 && y < size) {                        
  384.                     if (chessPanel[x][y] == null) {                                  
  385.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  386.                     }
  387.                     nextNode = chessPanel[x][y];
  388.                     if (!nextNode.isVisited()) {                                  
  389.                         nextNode.setVisited(true);                                
  390.                         nextNode.setStep(step + 1);                          
  391.                         queue.addLast(nextNode);                                
  392.                     }
  393.                 }
  394.                 x = Currentnode.getX() - 1;
  395.                 y = Currentnode.getY() + 2;
  396.                 step = Currentnode.getStep();                                  
  397.                 if (x >= 0 && x < size && y >= 0 && y < size) {                  
  398.                     if (chessPanel[x][y] == null) {                                  
  399.                         chessPanel[x][y] = new chessNode(x, y, false, 0, false);
  400.                     }
  401.                     nextNode = chessPanel[x][y];
  402.                     if (!nextNode.isVisited()) {                                  
  403.                         nextNode.setVisited(true);                  
  404.                         nextNode.setStep(step + 1);
  405.                         queue.addLast(nextNode);  
  406.                     }
  407.                 }
  408.                 break;
  409.             default:
  410.         }
  411.  
  412.         }
  413.     }
  414.  
  415.     public static void main(String[] args) {
  416.         int size = 5000; // array
  417.         int startX = 2000;
  418.         int startY = 3000;
  419.         int endX = 1000;
  420.         int endY = 600;
  421.  
  422.         chessNode[][] chessPanel = new chessNode[size][size];                 // Set Buffer Size
  423.         chessPanel[endX][endY] = new chessNode(endX, endY, false, 0, true);   // Set Target Node
  424.         BFS(startX, startY, chessPanel, size,endX,endY);
  425.         System.out.println(chessPanel[endX][endY].getStep());
  426.  
  427.     }
  428. }
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446. /*      
  447.    0|0        startX < targetX == go right
  448.   0 | 0       starty == targety == go up and down
  449. ----x-T--     4 node to travel
  450.   0 | 0
  451.    0|0
  452.  
  453.    0|1  
  454.   0 | 1    
  455. ----V-T--    
  456.   0 | 1
  457.    0|1
  458.  
  459.    0|1  
  460.   0 | 1
  461. ----V-2--  Found
  462.   0 | 1
  463.    0|1
  464.  
  465. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!