Number maze

Problem

Solution

/*

============================================================================

Author : James Chen

Email : a.james.chen@gmail.com

Description : Number maze

Created Date : 13-September-2013

Last Modified :

============================================================================

*/

#include <iostream>

#include <iomanip>

#include <set>

#include <vector>

#include <queue>

using namespace std;

typedef pair<int, int> point;

void FindPath(int *maze, vector<point>& path, set<point>& visited, point& visiting, bool& found)

{

if(found) return;

if(visiting.first == 4 && visiting.second == 4){

cout << "The path is : " << endl;

for(auto it: path){

cout << "[" << it.first << ", ";

cout << it.second << "]";

cout << " = " << maze[it.second * 9 + it.first];

cout << endl;

}

cout << "[4, 4] = H" << endl;

found = true;

return;

}

int steps = maze[visiting.second * 9 + visiting.first];

point newStarts[4] = {

make_pair(visiting.first - steps, visiting.second),

make_pair(visiting.first + steps, visiting.second),

make_pair(visiting.first, visiting.second - steps),

make_pair(visiting.first, visiting.second + steps)

};

for(int i = 0; i < sizeof(newStarts) /sizeof(newStarts[0]); ++i ){

if(newStarts[i].first >= 0 && newStarts[i].first <= 8 &&

newStarts[i].second >= 0 && newStarts[i].second <= 8){

if(visited.find(newStarts[i]) == visited.end()){

visited.insert(newStarts[i]);

path.push_back(newStarts[i]);

FindPath(maze, path, visited, newStarts[i], found);

path.pop_back();

}

}

}

}

int main(int argc, char* argv[])

{

int maze[][9] =

{

{3, 5, 4, 4, 7, 3, 4, 6, 3},

{6, 7, 5, 6, 6, 2, 6, 6, 2},

{3, 3, 4, 3, 2, 5, 4, 7, 2},

{6, 5, 5, 1, 2, 3, 6, 5, 6},

{3, 3, 4, 3, 0, 1, 4, 3, 4},

{3, 5, 4, 3, 2, 2, 3, 3, 5},

{3, 5, 4, 3, 2, 6, 4, 4, 3},

{3, 5, 1, 3, 7, 5, 3, 6, 4},

{6, 2, 4, 3, 4, 5, 4, 5, 1}

};

// print number maze

cout << "The number maze " << endl;

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

for(int j = 0; j < 9; ++j){

cout << setw(3) << maze[i][j];

}

cout << endl;

}

vector<point> path;

set<point> visited;

queue<point> visiting;

bool found = false;

point starts[4] = {

make_pair(0, 0),

make_pair(0, 8),

make_pair(8, 0),

make_pair(8, 8)

};

for(int i = 0; i < sizeof(starts) /sizeof(starts[0]) && !found; ++i ){

path.push_back(starts[i]);

FindPath((int *)&maze[0][0], path, visited, starts[i], found);

path.pop_back();

}

return 0;

}

Output

The number maze

3 5 4 4 7 3 4 6 3

6 7 5 6 6 2 6 6 2

3 3 4 3 2 5 4 7 2

6 5 5 1 2 3 6 5 6

3 3 4 3 0 1 4 3 4

3 5 4 3 2 2 3 3 5

3 5 4 3 2 6 4 4 3

3 5 1 3 7 5 3 6 4

6 2 4 3 4 5 4 5 1

The path is :

[0, 0] = 3

[3, 0] = 4

[7, 0] = 6

[7, 6] = 4

[3, 6] = 3

[3, 3] = 1

[4, 3] = 2

[4, 5] = 2

[2, 5] = 4

[2, 1] = 5

[7, 1] = 6

[7, 7] = 6

[1, 7] = 5

[1, 2] = 3

[4, 2] = 2

[4, 4] = 0

[4, 4] = H

Press any key to continue . . .