Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include <iostream>
- #include<string.h>
- #include <stdlib.h>
- using namespace std;
- //Check whether exists a path for pushing the box with a direction.
- int checkPush(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction);
- //Check whether exists a path for pulling the box with a direction.
- int checkPull(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction);
- //Check whether the robot can move to a specific position or not
- void checkMovementOfRobo(int a[50][50], int m, int n, int iRobot, int jRobot, int iDestination, int jDestination, int energy);
- //Find all the paths
- 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);
- //Find how many spots the box will move when pushing it.
- int findAllRightPush(int a[50][50], int m, int n, int iBox, int jBox);
- int findAllLeftPush(int a[50][50], int m, int n, int iBox, int jBox);
- int findAllTopPush(int a[50][50], int m, int n, int iBox, int jBox);
- int findAllBottomPush(int a[50][50], int m, int n, int iBox, int jBox);
- //Find the energy for the robot move to a particular position
- int tempEnergy;
- int getEnergyRobotMove(int a[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iDestiation, int jDestination);
- int energyOfSolutions[1000];
- int indexOfEnergy = 0;
- int C = 3;
- int main() {
- int a[50][50] = {
- {0, 0, 0, 1, 1, 0 ,0 ,0},
- {1, 1, 1, 1, 1, 1, 0, 0},
- {0, 0, 0, 0, 1, 0, 0, 0},
- {1, 1, 1, 0, 1, 1, 0, 0},
- {1, 1, 1, 1, 1, 1, 0, 0},
- {1, 1, 0, 0, 0, 0, 0, 0}
- };
- int visitedSpot[50][50] = {
- {0, 0, 0, 1, 1, 0 ,0 ,0},
- {1, 1, 1, 1, 1, 1, 0, 0},
- {0, 0, 0, 0, 1, 0, 0, 0},
- {1, 1, 1, 0, 1, 1, 0, 0},
- {1, 1, 1, 1, 1, 1, 0, 0},
- {1, 1, 0, 0, 0, 0, 0, 0}
- };
- int m = 6;
- int n = 8;
- int iRobot = 1, jRobot = 0;
- int iBox = 1, jBox = 1;
- int iDestination = 5, jDestination = 0;
- visitedSpot[iBox][jBox] = 0;
- findPath(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, iDestination, jDestination, 0);
- int minEnergy = energyOfSolutions[0];
- for(int i = 1; i < indexOfEnergy; i++) {
- if(minEnergy > energyOfSolutions[i])
- minEnergy = energyOfSolutions[i];
- }
- cout << minEnergy;
- return 0;
- }
- 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) {
- if(iBox == iSpot && jBox == jSpot) {
- energyOfSolutions[indexOfEnergy++] = totalEnergy;
- }
- else {
- if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'L')) {
- //cout << iRobot << " " << jRobot << " " << iBox << " " << jBox << " " << getEnergyRobotMove(a, m, n, iRobot, jRobot, iBox, jBox, iBox, jBox + 1) << " " << totalEnergy << "\n";
- int moveLeft = findAllLeftPush(a, m, n, iBox, jBox);
- visitedSpot[iBox][moveLeft] = 0;
- 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);
- visitedSpot[iBox][moveLeft] = 1;
- }
- if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
- int moveRight = findAllRightPush(a, m, n, iBox, jBox);
- visitedSpot[iBox][moveRight] = 0;
- 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);
- visitedSpot[iBox][moveRight] = 1;
- }
- if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
- int moveTop = findAllTopPush(a, m, n, iBox, jBox);
- visitedSpot[moveTop][jBox] = 0;
- 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);
- visitedSpot[moveTop][jBox] = 1;
- }
- if(checkPush(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
- int moveBottom = findAllBottomPush(a, m, n, iBox, jBox);
- visitedSpot[moveBottom][jBox] = 0;
- 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);
- visitedSpot[moveBottom][jBox] = 1;
- }
- //Pulling the box
- if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'L')) {
- visitedSpot[iBox][jBox - 1] = 0;
- 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);
- visitedSpot[iBox][jBox - 1] = 1;
- }
- if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'R')) {
- visitedSpot[iBox][jBox + 1] = 0;
- 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);
- visitedSpot[iBox][jBox + 1] = 1;
- }
- if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'T')) {
- visitedSpot[iBox - 1][jBox] = 0;
- 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);
- visitedSpot[iBox - 1][jBox] = 1;
- }
- if(checkPull(a, visitedSpot, m, n, iRobot, jRobot, iBox, jBox, 'B')) {
- visitedSpot[iBox + 1][jBox] = 0;
- 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);
- visitedSpot[iBox + 1][jBox] = 1;
- }
- }
- }
- int findAllRightPush(int a[50][50], int m, int n, int iBox, int jBox) {
- while(jBox + 1 < n && a[iBox][jBox + 1] == 1) {
- jBox++;
- }
- return jBox;
- }
- int findAllLeftPush(int a[50][50], int m, int n, int iBox, int jBox) {
- while(jBox - 1 >= 0 && a[iBox][jBox - 1] == 1) {
- jBox--;
- }
- return jBox;
- }
- int findAllTopPush(int a[50][50], int m, int n, int iBox, int jBox) {
- while(iBox - 1 >= 0 && a[iBox - 1][jBox] == 1) {
- iBox--;
- }
- return iBox;
- }
- int findAllBottomPush(int a[50][50], int m, int n, int iBox, int jBox) {
- while(iBox + 1 < m && a[iBox + 1][jBox] == 1) {
- iBox++;
- }
- return iBox;
- }
- //Check whether the robot can move to a specific position or not
- void checkMovementOfRobo(int a[50][50], int m, int n, int iRobot, int jRobot, int iDestination, int jDestination, int energy) {
- if(iRobot == iDestination && jRobot == jDestination) {
- if(tempEnergy == 0)
- tempEnergy = energy;
- else if(tempEnergy > energy)
- tempEnergy = energy;
- }
- else {
- if(jRobot - 1 >= 0 && a[iRobot][jRobot - 1] == 1) {
- a[iRobot][jRobot - 1] = 0;
- checkMovementOfRobo(a, m, n, iRobot, jRobot - 1, iDestination, jDestination, energy + 1);
- a[iRobot][jRobot - 1] = 1;
- }
- if(jRobot + 1 < n && a[iRobot][jRobot + 1] == 1) {
- a[iRobot][jRobot + 1] = 0;
- checkMovementOfRobo(a, m, n, iRobot, jRobot + 1, iDestination, jDestination, energy + 1);
- a[iRobot][jRobot + 1] = 1;
- }
- if(iRobot - 1 >= 0 && a[iRobot - 1][jRobot] == 1) {
- a[iRobot - 1][jRobot] = 0;
- checkMovementOfRobo(a, m, n, iRobot - 1, jRobot, iDestination, jDestination, energy + 1);
- a[iRobot - 1][jRobot] = 1;
- }
- if(iRobot + 1 < m && a[iRobot + 1][jRobot] == 1) {
- a[iRobot + 1][jRobot] = 0;
- checkMovementOfRobo(a, m, n, iRobot + 1, jRobot, iDestination, jDestination, energy + 1);
- a[iRobot + 1][jRobot] = 1;
- }
- }
- }
- int getEnergyRobotMove(int a[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, int iDestination, int jDestination) {
- tempEnergy = 0;
- int temp[50][50];
- for(int i = 0; i < m; i++) {
- for(int j = 0; j < n; j++) {
- temp[i][j] = a[i][j];
- }
- }
- temp[iBox][jBox] = 0;
- checkMovementOfRobo(a, m, n, iRobot, jRobot, iDestination, jDestination, 0);
- temp[iBox][jBox] = 1;
- return tempEnergy;
- }
- //Check whether exists a path for pushing the box with a direction.
- int checkPush(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
- if(direction == 'L') {
- if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] && iRobot == iBox && jRobot == jBox + 1)
- return 1;
- 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);
- }
- else if(direction == 'R') {
- if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iBox && jRobot == iBox - 1)
- return 1;
- 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);
- }
- else if(direction == 'T') {
- if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
- return 1;
- 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);
- }
- else {
- if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
- return 1;
- 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);
- }
- }
- //Check whether exists a path for pulling the box with a direction.
- int checkPull(int a[50][50], int visitedSpot[50][50], int m, int n, int iRobot, int jRobot, int iBox, int jBox, char direction) {
- if(direction == 'L') {
- if(jBox - 1 >= 0 && visitedSpot[iBox][jBox - 1] == 1 && iRobot == iBox && jRobot == jBox - 1)
- return 1;
- 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);
- }
- else if(direction == 'R'){
- if(jBox + 1 < n && visitedSpot[iBox][jBox + 1] == 1 && iRobot == iRobot && jRobot == jBox + 1)
- return 1;
- 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);
- }
- else if(direction == 'T') {
- if(iBox - 1 >= 0 && visitedSpot[iBox - 1][jBox] == 1 && iRobot == iBox - 1 && jRobot == jBox)
- return 1;
- 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);
- }
- else {
- if(iBox + 1 < m && visitedSpot[iBox + 1][jBox] == 1 && iRobot == iBox + 1 && jRobot == jBox)
- return 1;
- 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);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement