API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 21st, 2018
97
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.46 KB | None | 0 0
raw download clone embed print report
  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.         {0, 0, 0, 0, 1, 1, 0, 0},
  40.         {0, 1, 1, 1, 1, 1, 0, 0},
  41.         {0, 0, 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.         {0, 0, 0, 0, 1, 1, 0, 0},
  49.         {0, 1, 1, 1, 1, 1, 0, 0},
  50.         {0, 0, 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 = 4, jDestination = 1;
  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.             int moveLeft = findAllLeftPush(a, m, n, iBox, jBox);
  81.             visitedSpot[iBox][moveLeft] = 0;
  82.             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);
  83.             visitedSpot[iBox][moveLeft] = 1;
  84.            
  85.         }
  86.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
  87.             int moveRight = findAllRightPush(a, m, n, iBox, jBox);
  88.             visitedSpot[iBox][moveRight] = 0;
  89.             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);
  90.             visitedSpot[iBox][moveRight] = 1;  
  91.         }
  92.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
  93.             int moveTop = findAllTopPush(a, m, n, iBox, jBox);
  94.             visitedSpot[moveTop][jBox] = 0;
  95.             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);
  96.             visitedSpot[moveTop][jBox] = 1;
  97.         }
  98.         if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
  99.            
  100.             int moveBottom = findAllBottomPush(a, m, n, iBox, jBox);
  101.             visitedSpot[moveBottom][jBox] = 0;
  102.             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);
  103.             visitedSpot[moveBottom][jBox] = 1;
  104.         }
  105.        
  106.         //Pulling the box
  107.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'L')) {
  108.             visitedSpot[iBox][jBox - 1] = 0;
  109.             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);
  110.             visitedSpot[iBox][jBox - 1] = 1;
  111.         }
  112.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
  113.             visitedSpot[iBox][jBox + 1] = 0;
  114.             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);
  115.             visitedSpot[iBox][jBox + 1] = 1;
  116.         }
  117.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
  118.             visitedSpot[iBox - 1][jBox] = 0;
  119.             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);
  120.             visitedSpot[iBox - 1][jBox] = 1;
  121.         }
  122.         if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
  123.             visitedSpot[iBox + 1][jBox] = 0;
  124.             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);
  125.             visitedSpot[iBox + 1][jBox] = 1;
  126.         }
  127.     }
  128.  
  129. }
  130.  
  131. int findAllRightPush(int a[50][50], int m, int n, int iBox, int jBox) {
  132.     while(jBox + 1 < n && a[iBox][jBox + 1] == 1) {
  133.         jBox++;
  134.     }
  135.     return jBox;
  136. }
  137.  
  138. int findAllLeftPush(int a[50][50], int m, int n, int iBox, int jBox) {
  139.     while(jBox - 1 >= 0 && a[iBox][jBox - 1] == 1) {
  140.         jBox--;
  141.     }
  142.     return jBox;
  143. }
  144.  
  145. int findAllTopPush(int a[50][50], int m, int n, int iBox, int jBox) {
  146.     while(iBox - 1 >= 0 && a[iBox - 1][jBox] == 1) {
  147.         iBox--;
  148.     }
  149.     return iBox;
  150. }
  151.  
  152. int findAllBottomPush(int a[50][50], int m, int n, int iBox, int jBox) {
  153.     while(iBox + 1 < m && a[iBox + 1][jBox] == 1) {
  154.         iBox++;
  155.     }
  156.     return iBox;
  157. }
  158.  
  159. //Check whether the robot can move to a specific position or not
  160. void checkMovementOfRobo(int a[50][50], int m, int n, int iRobot, int jRobot, int iDestination, int jDestination, int energy) {
  161.    
  162.     if(iRobot == iDestination && jRobot == jDestination) {
  163.         if(tempEnergy == 0)
  164.             tempEnergy = energy;
  165.         else if(tempEnergy > energy)
  166.             tempEnergy = energy;
  167.     }
  168.     else {
  169.         if(jRobot - 1 >= 0 && a[iRobot][jRobot - 1] == 1) {
  170.             a[iRobot][jRobot - 1] = 0;
  171.             checkMovementOfRobo(a, m, n, iRobot, jRobot - 1, iDestination, jDestination, energy + 1);
  172.             a[iRobot][jRobot - 1] = 1;
  173.         }
  174.         if(jRobot + 1 < n && a[iRobot][jRobot + 1] == 1) {
  175.             a[iRobot][jRobot + 1] = 0;
  176.             checkMovementOfRobo(a, m, n, iRobot, jRobot + 1, iDestination, jDestination, energy + 1);
  177.             a[iRobot][jRobot + 1] = 1;
  178.         }
  179.         if(iRobot - 1 >= 0 && a[iRobot - 1][jRobot] == 1) {
  180.             a[iRobot - 1][jRobot] = 0;
  181.             checkMovementOfRobo(a, m, n, iRobot - 1, jRobot, iDestination, jDestination, energy + 1);
  182.             a[iRobot - 1][jRobot] = 1;
  183.         }
  184.         if(iRobot + 1 < m && a[iRobot + 1][jRobot] == 1) {
  185.             a[iRobot + 1][jRobot] = 0;
  186.             checkMovementOfRobo(a, m, n, iRobot + 1, jRobot, iDestination, jDestination, energy + 1);
  187.             a[iRobot + 1][jRobot] = 1;
  188.         }
  189.     }
  190. }
  191.  
  192. int getEnergyRobotMove(int a[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iDestination, int jDestination) {
  193.     tempEnergy = 0;
  194.     int temp[50][50];
  195.     for(int i = 0; i < m; i++) {
  196.         for(int j = 0; j < n; j++) {
  197.             temp[i][j] = a[i][j];
  198.         }
  199.     }
  200.     temp[iBox][jBox] = 0;
  201.     checkMovementOfRobo(a, m, n, iRobot, jRobot, iDestination, jDestination, 0);
  202.     temp[iBox][jBox] = 1;
  203.     return tempEnergy;
  204. }
  205.  
  206. //Check whether exists a path for pushing the box with a direction.
  207. int checkPush(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
  208.     if(direction == 'L') {
  209.         if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] && iRobot == iBox && jRobot == jBox + 1)
  210.             return 1;
  211.         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);
  212.     }
  213.     else if(direction == 'R') {
  214.         if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iBox && jRobot == iBox - 1)
  215.             return 1;
  216.         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);
  217.     }
  218.     else if(direction == 'T') {
  219.         if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
  220.             return 1;
  221.         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);
  222.     }
  223.     else {
  224.         if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
  225.             return 1;
  226.         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);
  227.     }
  228. }
  229.  
  230. //Check whether exists a path for pulling the box with a direction.
  231. int checkPull(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
  232.     if(direction == 'L') {
  233.         if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] == 1 && iRobot == iBox && jRobot == jBox - 1)
  234.             return 1;
  235.         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);
  236.     }
  237.     else if(direction == 'R'){
  238.         if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iRobot && jRobot == jBox + 1)
  239.             return 1;
  240.         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);
  241.     }
  242.     else if(direction == 'T') {
  243.         if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
  244.             return 1;
  245.         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);
  246.     }
  247.     else {
  248.         if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
  249.             return 1;
  250.         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);
  251.     }
  252. }
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!