Advertisement
Guest User

Untitled

a guest
Jun 21st, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.65 KB | None | 0 0
  1. #include<stdio.h>
  2. #include <iostream>
  3. #include<string.h>
  4. #include <stdlib.h>
  5. using namespace std;
  6.  
  7. //Check whether exists a path for pushing the box with a direction.
  8. int checkPush(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction);
  9.  
  10. //Check whether exists a path for pulling the box with a direction.
  11. int checkPull(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction);
  12.  
  13. //Check whether the robot can move to a specific position or not
  14. void checkMovementOfRobo(int a[50][50], int m, int n, int iRobot, int jRobot, int iDestination, int jDestination, int energy);
  15.  
  16. //Find all the paths
  17. void findPath(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iSpot, int jSpot, int totalEnergy);
  18.  
  19. //Find how many spots the box will move when pushing it.
  20. int findAllRightPush(int a[50][50], int m, int n, int iBox, int jBox);
  21. int findAllLeftPush(int a[50][50], int m, int n, int iBox, int jBox);
  22. int findAllTopPush(int a[50][50], int m, int n, int iBox, int jBox);
  23. int findAllBottomPush(int a[50][50], int m, int n, int iBox, int jBox);
  24.  
  25. //Find the energy for the robot move to a particular position
  26. int tempEnergy;
  27. int getEnergyRobotMove(int a[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iDestiation, int jDestination);
  28.  
  29.  
  30. int energyOfSolutions[1000];
  31. int indexOfEnergy = 0;
  32. int C = 3;
  33.  
  34. int main() {
  35.     int a[50][50] = {
  36.         {0, 0, 0, 1, 1, 0 ,0 ,0},
  37.         {1, 1, 1, 1, 1, 1, 0, 0},
  38.         {0, 0, 0, 0, 1, 0, 0, 0},
  39.         {1, 1, 1, 0, 1, 1, 0, 0},
  40.         {1, 1, 1, 1, 1, 1, 0, 0},
  41.         {1, 1, 0, 0, 0, 0, 0, 0}
  42.     };
  43.    
  44.     int visitedSpot[50][50] = {
  45.         {0, 0, 0, 1, 1, 0 ,0 ,0},
  46.         {1, 1, 1, 1, 1, 1, 0, 0},
  47.         {0, 0, 0, 0, 1, 0, 0, 0},
  48.         {1, 1, 1, 0, 1, 1, 0, 0},
  49.         {1, 1, 1, 1, 1, 1, 0, 0},
  50.         {1, 1, 0, 0, 0, 0, 0, 0}
  51.     };
  52.    
  53.     int m = 6;
  54.     int n = 8;
  55.    
  56.     int iRobot = 1, jRobot = 0;
  57.     int iBox = 1, jBox = 1;
  58.     int iDestination = 5, jDestination = 0;
  59.    
  60.     visitedSpot[iBox][jBox] = 0;
  61.     findPath(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, iDestination, jDestination, 0);
  62.    
  63.     int minEnergy = energyOfSolutions[0];
  64.     for(int i = 1; i < indexOfEnergy; i++) {
  65.         if(minEnergy > energyOfSolutions[i])
  66.             minEnergy = energyOfSolutions[i];
  67.     }
  68.    
  69.     cout << minEnergy;
  70.    
  71.     return 0;
  72. }
  73.  
  74. void findPath(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iSpot, int jSpot, int totalEnergy) {
  75.     if(iBox == iSpot && jBox == jSpot) {
  76.         energyOfSolutions[indexOfEnergy++] = totalEnergy;
  77.     }
  78.     else {
  79.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'L')) {
  80.             //cout << iRobot << " " << jRobot << " " << iBox << " " << jBox << " " << getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) << " " << totalEnergy << "\n";
  81.             int moveLeft = findAllLeftPush(a, m, n, iBox, jBox);
  82.             visitedSpot[iBox][moveLeft] = 0;
  83.             findPath(a, visitedSpot, m, n, iBox, jBox + 1, iBox, moveLeft, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) + C);
  84.             visitedSpot[iBox][moveLeft] = 1;
  85.            
  86.         }
  87.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
  88.            
  89.             int moveRight = findAllRightPush(a, m, n, iBox, jBox);
  90.             visitedSpot[iBox][moveRight] = 0;
  91.             findPath(a, visitedSpot, m, n, iBox, jBox - 1, iBox, moveRight, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox - 1) + C);
  92.             visitedSpot[iBox][moveRight] = 1;  
  93.         }
  94.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
  95.             int moveTop = findAllTopPush(a, m, n, iBox, jBox);
  96.             visitedSpot[moveTop][jBox] = 0;
  97.             findPath(a, visitedSpot, m, n, iBox + 1, jBox, moveTop, jBox , iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox + 1, jBox) + C);
  98.             visitedSpot[moveTop][jBox] = 1;
  99.         }
  100.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
  101.            
  102.             int moveBottom = findAllBottomPush(a, m, n, iBox, jBox);
  103.             visitedSpot[moveBottom][jBox] = 0;
  104.             findPath(a, visitedSpot, m, n, iBox - 1, jBox, moveBottom, jBox, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox - 1, jBox) + C);
  105.             visitedSpot[moveBottom][jBox] = 1;
  106.         }
  107.        
  108.         //Pulling the box
  109.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'L')) {
  110.            
  111.             visitedSpot[iBox][jBox - 1] = 0;
  112.             findPath(a, visitedSpot, m, n, iBox, jBox - 2, iBox, jBox - 1, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox - 1) + C);
  113.             visitedSpot[iBox][jBox - 1] = 1;
  114.         }
  115.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
  116.             visitedSpot[iBox][jBox + 1] = 0;
  117.             findPath(a, visitedSpot, m, n, iBox, jBox + 2, iBox, jBox + 1, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) + C);
  118.             visitedSpot[iBox][jBox + 1] = 1;
  119.         }
  120.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
  121.             visitedSpot[iBox - 1][jBox] = 0;
  122.             findPath(a, visitedSpot, m, n, iBox - 2, jBox, iBox - 1, jBox, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox - 1, jBox) + C);
  123.             visitedSpot[iBox - 1][jBox] = 1;
  124.         }
  125.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
  126.             visitedSpot[iBox + 1][jBox] = 0;
  127.             findPath(a, visitedSpot, m, n, iBox + 2, jBox, iBox + 1, jBox, iSpot, jSpot, totalEnergy + getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox + 1, jBox) + C);
  128.             visitedSpot[iBox + 1][jBox] = 1;
  129.         }
  130.     }
  131.    
  132.  
  133. }
  134.  
  135. int findAllRightPush(int a[50][50], int m, int n, int iBox, int jBox) {
  136.     while(jBox + 1 < n && a[iBox][jBox + 1] == 1) {
  137.         jBox++;
  138.     }
  139.     return jBox;
  140. }
  141.  
  142. int findAllLeftPush(int a[50][50], int m, int n, int iBox, int jBox) {
  143.     while(jBox - 1 >= 0 && a[iBox][jBox - 1] == 1) {
  144.         jBox--;
  145.     }
  146.     return jBox;
  147. }
  148.  
  149. int findAllTopPush(int a[50][50], int m, int n, int iBox, int jBox) {
  150.     while(iBox - 1 >= 0 && a[iBox - 1][jBox] == 1) {
  151.         iBox--;
  152.     }
  153.     return iBox;
  154. }
  155.  
  156. int findAllBottomPush(int a[50][50], int m, int n, int iBox, int jBox) {
  157.     while(iBox + 1 < m && a[iBox + 1][jBox] == 1) {
  158.         iBox++;
  159.     }
  160.     return iBox;
  161. }
  162.  
  163. //Check whether the robot can move to a specific position or not
  164. void checkMovementOfRobo(int a[50][50], int m, int n, int iRobot, int jRobot, int iDestination, int jDestination, int energy) {
  165.    
  166.     if(iRobot == iDestination && jRobot == jDestination) {
  167.         if(tempEnergy == 0)
  168.             tempEnergy = energy;
  169.         else if(tempEnergy > energy)
  170.             tempEnergy = energy;
  171.     }
  172.     else {
  173.         if(jRobot - 1 >= 0 && a[iRobot][jRobot - 1] == 1) {
  174.             a[iRobot][jRobot - 1] = 0;
  175.             checkMovementOfRobo(a, m, n, iRobot, jRobot - 1, iDestination, jDestination, energy + 1);
  176.             a[iRobot][jRobot - 1] = 1;
  177.         }
  178.         if(jRobot + 1 < n && a[iRobot][jRobot + 1] == 1) {
  179.             a[iRobot][jRobot + 1] = 0;
  180.             checkMovementOfRobo(a, m, n, iRobot, jRobot + 1, iDestination, jDestination, energy + 1);
  181.             a[iRobot][jRobot + 1] = 1;
  182.         }
  183.         if(iRobot - 1 >= 0 && a[iRobot - 1][jRobot] == 1) {
  184.             a[iRobot - 1][jRobot] = 0;
  185.             checkMovementOfRobo(a, m, n, iRobot - 1, jRobot, iDestination, jDestination, energy + 1);
  186.             a[iRobot - 1][jRobot] = 1;
  187.         }
  188.         if(iRobot + 1 < m && a[iRobot + 1][jRobot] == 1) {
  189.             a[iRobot + 1][jRobot] = 0;
  190.             checkMovementOfRobo(a, m, n, iRobot + 1, jRobot, iDestination, jDestination, energy + 1);
  191.             a[iRobot + 1][jRobot] = 1;
  192.         }
  193.     }
  194. }
  195.  
  196. int getEnergyRobotMove(int a[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iDestination, int jDestination) {
  197.     tempEnergy = 0;
  198.     int temp[50][50];
  199.     for(int i = 0; i < m; i++) {
  200.         for(int j = 0; j < n; j++) {
  201.             temp[i][j] = a[i][j];
  202.         }
  203.     }
  204.     temp[iBox][jBox] = 0;
  205.     checkMovementOfRobo(a, m, n, iRobot, jRobot, iDestination, jDestination, 0);
  206.     temp[iBox][jBox] = 1;
  207.     return tempEnergy;
  208. }
  209.  
  210. //Check whether exists a path for pushing the box with a direction.
  211. int checkPush(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
  212.     if(direction == 'L') {
  213.         if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] && iRobot == iBox && jRobot == jBox + 1)
  214.             return 1;
  215.         return (jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] == 1 && a[iBox][jBox + 1] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) != 0);
  216.     }
  217.     else if(direction == 'R') {
  218.         if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iBox && jRobot == iBox - 1)
  219.             return 1;
  220.         return (jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && a[iBox][jBox - 1] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox - 1) != 0);
  221.     }
  222.     else if(direction == 'T') {
  223.         if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
  224.             return 1;
  225.         return (iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && a[iBox + 1][jBox] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox + 1, jBox) != 0);
  226.     }
  227.     else {
  228.         if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
  229.             return 1;
  230.         return (iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && a[iBox - 1][jBox] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox - 1, jBox) != 0);
  231.     }
  232. }
  233.  
  234. //Check whether exists a path for pulling the box with a direction.
  235. int checkPull(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
  236.     if(direction == 'L') {
  237.         if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] == 1 && iRobot == iBox && jRobot == jBox - 1)
  238.             return 1;
  239.         return (jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] == 1 && a[iBox][jBox - 2] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox - 1) != 0);
  240.     }
  241.     else if(direction == 'R'){
  242.         if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iRobot && jRobot == jBox + 1)
  243.             return 1;
  244.         return (jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && a[iBox][jBox + 2] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) != 0);
  245.     }
  246.     else if(direction == 'T') {
  247.         if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
  248.             return 1;
  249.         return (iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && a[iBox - 2][jBox] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox - 1, jBox) != 0);
  250.     }
  251.     else {
  252.         if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
  253.             return 1;
  254.         return (iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && a[iBox + 2][jBox] == 1 && getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox + 1, jBox) != 0);
  255.     }
  256. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement