// mazeSolver.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int SIZE=5;


int findStart(char m[SIZE][SIZE])
{
    int col=0;
    int row=0;
    for(row=0; row <SIZE;row++)
        if(m[row][col] == 's' || m[row][col] == 'S')
            return row;
    return 0;
}

int* findExits(char m[SIZE][SIZE])
{   int* exits=new int[SIZE];
    int col=0;
    int row=0;
    int i=0;
    for(row=0; row <SIZE;row++)
        if(m[row][SIZE-1] !='#'){
            exits[i]=row;

            i++;
        }
    return exits;
}

bool findPath(char m[SIZE][SIZE],int row,int col,int* exitrow,int curCol,int curRow,bool s[SIZE][SIZE])
{
    s[curRow][curCol]=true;



    if(m[curRow][curCol] =='#' || curCol < 0 || curRow <1 || (curRow> (SIZE-2)) )
        return false;
    cout<<m[curRow][curCol];

    for(int i=0;i<2;i++)
        if( curRow==exitrow[i] && curCol == SIZE-1){
            cout<<endl;
            m[curRow][curCol]='#';
            curCol=col;
            curRow=row;
            findPath(m,row,col,exitrow,curCol,curRow,s);
            for(int i=0; i<SIZE;i++)
                for(int j=0; j<SIZE;j++)
                    s[i][j]=false;
            return true;
        }


        if(findPath(m,row,col,exitrow,curCol+1,curRow,s) && s[curRow][curCol]==false)
            //east
            return true;

        if(findPath(m,row,col,exitrow,curCol,curRow+1,s) && s[curRow][curCol]==false)
            return true;//south

        if(findPath(m,row,col,exitrow,curCol,curRow-1,s)&& s[curRow][curCol]==false)
            return true;//north
        if(findPath(m,row,col,exitrow,curCol-1,curRow,s)&& s[curRow][curCol]==false)
            return true;//west

        return false;

}

void generate_all_paths(char m[SIZE][SIZE],bool s[SIZE][SIZE])
{   int startrow=findStart(m);
    cout<<"start row "<<startrow<<endl;
    int* exitRows=findExits(m);

        for(int i=0; i< sizeof(exitRows)/sizeof(int);i++)
        cout<<"exit row "<<exitRows[i]<<" "<<endl;
        findPath(m,startrow,0,exitRows,0,startrow,s);
}

int main(){
    //actual maze
    char m[SIZE][SIZE];
    //marking maze
    bool sign[SIZE][SIZE];
    for(int i=0; i<SIZE;i++)
        for(int j=0; j<SIZE;j++)
            sign[i][j]=false;

    ifstream maze("maze.txt");
    string line;
    for(int i=0; i<SIZE;i++){
        getline(maze, line);
        for(int j=0; j<SIZE;j++){
            m[i][j]=line[j];
        }
    }


    for(int i=0; i<SIZE;i++){

        for(int j=0; j<SIZE;j++){
            cout<<m[i][j];
        }
        cout<<endl;
    }

    generate_all_paths(m,sign);

    return 0;
}