GO_HOME ?

As I was in the informatics Olympiad training pool sometime back. I used to be addicted in solving problems. This post is one such problem I solved on the 5th of May 2011 when I was bored. The problem is where a maze is given and a path needs to be found from a given source and a destination. The code was developed in 'Dev C++' .

//THE_CODE!!!!!

#include<iostream>
using namespace std;

const int mapWidth =10;
const int mapHeight=10;
char map[mapHeight][mapWidth]={' '};
int startY ;
int startX ;
int height, width;
int pathSteps=0;
int steps=0;
int tempSteps=0;
 
void displayMap(){
     for(int i=0;i<height;i++){
            for(int k=0;k<width;k++){
                    cout << map[i][k] ;
            }      
            cout << endl;
    }  
}

bool maze(int y, int x){
     if(y<0 || x<0 || y>height-1 || x>width-1){
            return false;    
     }  
     if(map[y][x]=='*' || map[y][x]=='d' ){
            return false;                            
     }
     if(y==startY && x==startX){
            return false;                
     }
     if(map[y][x]=='h'){
            cout << "FOUND! " << endl;
            return true;                            
     }
   
     map[y][x]='d';
     steps++;
   
     if(maze(y, x+1)){
            return true;        
     }
     if(maze(y+1, x)){
            return true;        
     }
     if(maze(y, x-1)){
            return true;        
     }
     if(maze(y-1, x)){
            return true;        
     }
     steps--;
     return false;
}


int main(){
    cin >> width;
    cin >> height;
    for(int i=0;i<height;i++){
            for(int k=0;k<width;k++){
                    cin >> map[i][k] ;
                    if(map[i][k]=='s'){
                              startY=i;
                              startX=k;                          
                    }
            }      
    }
    //displayMap();
    maze(startY, startX+1);
    tempSteps = steps;
    maze(startY+1, startX);
    if(steps<tempSteps){
            tempSteps = steps;                  
    }
    maze(startY-1, startX);
    if(steps<tempSteps){
            tempSteps = steps;                  
    }
    maze(startY, startX-1);
    if(steps<tempSteps){
            tempSteps = steps;                  
    }
    if(steps==0){
            cout << "NO PATH TO HOME!" <<  endl;          
    }else{
          cout << "Steps = " << steps << endl;
    }
    system("PAUSE");
    return 0;
}

//THE_INPUT

"

10

10

**********

*s****xx**

*x**xxx***

*xxxx*x***

*x****x***

*x****xx**

***hxxx***

**********

**********

**********

"

's' is the source;

'h' is destination;

'*' are blocks which cannot go through;

'x' are independent paths;

*Enter the above without quotes

//THE_OUTPUT

The output for the following maze, the number of steps needed to reach from 's' to 'd' is 14.

//DESCRIPTION

The solution is made using recursion. Rather than using 'for' loops, I thought it would be interesting to find the solution using recursion. The maze function solves the maze using each possible path. This algorithm does not find the shortest path.

Direct link to download the code - http://www.mediafire.com/?51yy0y8xb91kta7