Source code for submission s1190

grasshopper.cc

  1. //
  2. // File:   mosquito.cc
  3. // Author: cteam035
  4. //
  5. // Created on October 27, 2012, 11:23 AM
  6. //
  7.  
  8. #include <cstdlib>
  9. #include <cmath>
  10. #include <cstring>
  11. #include <string>
  12. #include <iostream>
  13. #include <stdio.h>
  14. #include <climits>
  15.  
  16.  
  17. using namespace std;
  18. //
  19. //
  20. //
  21.  
  22. int ** pole;
  23. int R, C;
  24. int xF, yF;
  25. int vysledek2;
  26.  
  27. void vypisPole() {
  28.     for (int i=0 ; i<R ; i++) {
  29.         for (int j=0 ; j<C ; j++) {
  30.             printf("%15d",pole[i][j]);
  31.         }
  32.         cout << endl;
  33.     }
  34. }
  35.  
  36.  
  37. int rekurze(int jump, int X, int Y) {
  38.     if ( pole[X][Y] < jump) {
  39.         return pole[X][Y];
  40.     }
  41.     if ( X == xF && Y == yF ) { //finish
  42.         pole[X][Y] = jump;
  43.         if ( jump < vysledek2 ) {
  44.             vysledek2 = jump;
  45.         }
  46.         return jump;
  47.     }
  48.     pole[X][Y] = jump;
  49.  
  50.     int ret = INT_MAX;
  51.     int tmpRet = INT_MAX;
  52.  
  53.     if ( X+2 < C && Y+1 < R) {
  54.         tmpRet = rekurze(jump+1, X+2, Y+1);
  55.         if (tmpRet < ret) {
  56.             ret = tmpRet;
  57.         }
  58.     }
  59.     if ( X+1 < C && Y+2 < R) {
  60.         tmpRet = rekurze(jump+1, X+1, Y+2);
  61.         if (tmpRet < ret) {
  62.             ret = tmpRet;
  63.         }
  64.     }
  65.     if ( X+2 < C && Y-1 >= 0) {
  66.         tmpRet = rekurze(jump+1, X+2, Y-1);
  67.         if (tmpRet < ret) {
  68.             ret = tmpRet;
  69.         }
  70.     }
  71.     if ( X+1 < C && Y-2 >= 0) {
  72.         tmpRet = rekurze(jump+1, X+1, Y-2);
  73.         if (tmpRet < ret) {
  74.             ret = tmpRet;
  75.         }
  76.     }
  77.     if ( X-2 >= 0 && Y+1 < R) {
  78.         tmpRet = rekurze(jump+1, X-2, Y+1);
  79.         if (tmpRet < ret) {
  80.             ret = tmpRet;
  81.         }
  82.     }
  83.     if ( X-1 >= 0 && Y+2 < R) {
  84.         tmpRet = rekurze(jump+1, X-1, Y+2);
  85.         if (tmpRet < ret) {
  86.             ret = tmpRet;
  87.         }
  88.     }
  89.     if ( X-1 >= 0 && Y-2 >= 0 ) {
  90.         tmpRet = rekurze(jump+1, X-1, Y-2);
  91.         if (tmpRet < ret) {
  92.             ret = tmpRet;
  93.         }
  94.     }
  95.     if ( X-2 >= 0 && Y-1 >= 0 ) {
  96.         tmpRet = rekurze(jump+1, X-2, Y-1);
  97.         if (tmpRet < ret) {
  98.             ret = tmpRet;
  99.         }
  100.     }
  101.  
  102.  
  103.     return ret;
  104.  
  105. }
  106.  
  107.  
  108. int main(int argc, char** argv) {
  109.  
  110.     int X1, X2, Y1, Y2;
  111.     int vysledek;
  112.  
  113.     while ( cin >> R >> C >> X1 >> Y1 >> X2 >> Y2 ) {
  114.         X1 -= 1;
  115.         X2 -= 1;
  116.         Y1 -= 1;
  117.         Y2 -= 1;
  118.         vysledek2 = INT_MAX;
  119.  
  120.  
  121.         pole = new int* [R];
  122.         for( int i=0 ; i<R ; i++) {
  123.             pole[i] = new int[C];
  124.             for (int j=0 ; j<C ; j++) {
  125.                 pole[i][j]=INT_MAX;
  126.             }
  127.         }
  128.  
  129.         xF = X2;
  130.         yF = Y2;
  131.  
  132.         vysledek = rekurze(0, X1, Y1);
  133.         if (vysledek == INT_MAX) {
  134.             cout << "impossible" << endl;
  135.         }
  136.         else {
  137.             cout << vysledek2 << endl;
  138.         }
  139.  
  140.  
  141.         //vypisPole();
  142.  
  143.     }
  144.  
  145.  
  146.  
  147.  
  148.     return (EXIT_SUCCESS);
  149. }
  150.  
  151.