# Commits

committed 20ac4c2

Basic solution implemented in C and C++.

• Participants

# Files changed (16)

`+MAZE SOLVER`
`+`
`+PROBLEM:`
`+========`
`+Write a C or C++ program to be a virtual maze walking mouse for a two dimensional maze of X columns and Y rows.`
`+int maze[x][y];`
`+maze[?][?] == 1 means empty corridor.`
`+maze[?][?] == 0 means solid wall.`
`+ `
`+The entry point is fixed from (1,0); (i.e. maze[1][0] will always be 1).`
`+The exit point is a 1 at the edge of the maze.`
`+The output of the program is a set of (x,y) coordinates that leads from entry (1,0) to (?,?) the exit.`
`+ `
`+Example:`
`+0,1,0,0,0,0,0,0,0,0,0`
`+0,1,1,1,1,1,1,0,0,0,0`
`+0,0,0,1,0,0,1,1,0,0,0`
`+0,0,1,1,0,0,1,0,0,0,0`
`+0,0,0,0,0,1,1,1,1,0,0`
`+0,0,1,1,1,1,0,0,1,0,0`
`+0,0,0,1,0,0,0,0,0,0,0`
`+Entry at (1,0)`
`+ `
`+Virtual mouse should print out below:`
`+Solution: (1,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(6,2)(6,3)(6,4)(5,4)(5,5)(4,5)(3,5)(3,6)`
`+Exit at (3,6)`
`+`
`+Instructions:`
`+·         Follow the K.I.S.S. concept.`
`+·         Readability first, performance next.(i.e. the more thinking needed to understand the code the lower the score).`
`+·         Minimum C++ approach (for readability and portability), keep it simple.(i.e. the more C++ specific expression the lower the score).`
`+·         Code should for the most part be self documenting.`
`+`
`+`
`+SOLUTION:`
`+=========`
`+The solver works by eliminating dead ends and is not optimized to find `
`+the shortest path (KISS requirement).`
`+`
`+A makefile is included so run make to compile the program.`
`+`
`+The maze.txt file contains the assigned maze and will be loaded and solved each`
`+time the program is run. Alter it to test different mazes. Note, that the format`
`+of the file must remain "the same", i.e. there must be no comma at the end of a line, `
`+only 0's, 1's and ',' are allowed (though whitespace should be ignored this was not `
`+tested) and there must be a new line at the end of the file.`
`+`
`+Kind regards`
`+`
`+Lazar Sumar`
`+`
`+Note: The C version of the program was derived from the C++ attempt and follows`
`+      a seemingly OO approach. Depending on the requirement it might be better`
`+      to rewrite it using structured programming. It was left as is due to references`
`+      to C++ in the instructions...`

# File C Solution/makefile

`+CC=gcc`
`+CFLAGS=-Wall`
`+LIB=`
`+EXEC=maze_solver`
`+`
`+\$(EXEC): maze_solver.c`
`+	\$(CC) \$(CFLAGS) -o \$(EXEC) maze_solver.c`

# File C Solution/maze.txt

`+0,1,0,0,0,0,0,0,0,0,0`
`+0,1,1,1,1,1,1,0,0,0,0`
`+0,0,0,1,0,0,1,1,0,0,0`
`+0,0,1,1,0,0,1,0,0,0,0`
`+0,0,0,0,0,1,1,1,1,0,0`
`+0,0,1,1,1,1,0,0,1,0,0`
`+0,0,0,1,0,0,0,0,0,0,0`

# File C Solution/maze_solver.c

`+/* Author: Lazar Sumar`
`+ * Date 27th March 2012`
`+ */`
`+#include <stdlib.h>`
`+#include <stdio.h>`
`+`
`+#define ERROR 0`
`+#define MAX_MAZE_X 1000`
`+#define MAX_MAZE_Y 1000`
`+`
`+typedef struct {`
`+    int x, y;`
`+} Coord;`
`+typedef Coord Direction;`
`+`
`+Direction left;`
`+Direction right;`
`+Direction up;`
`+Direction down;`
`+`
`+typedef struct {`
`+    int maze[MAX_MAZE_X][MAX_MAZE_Y];`
`+    Coord size;`
`+    Coord position;`
`+    int marker;`
`+    Coord lastPosition;`
`+} Maze;`
`+`
`+void initialize_globals() {`
`+    left.x = -1; left.y = 0;`
`+    right.x = 1; right.y = 0;`
`+    up.x = 0; up.y = -1;`
`+    down.x = 0; down.y = 1;`
`+}`
`+`
`+Coord add(Coord c1, Coord c2) {`
`+    Coord res;`
`+    res.x = c1.x + c2.x; res.y = c1.y + c2.y;`
`+    return res;`
`+}`
`+`
`+Coord sub(Coord c1, Coord c2) {`
`+    Coord res;`
`+    res.x = c1.x - c2.x; res.y = c1.y - c2.y;`
`+    return res;`
`+}`
`+`
`+int equal(Coord c1, Coord c2) {`
`+    return c1.x == c2.x && c1.y == c2.y;`
`+}`
`+`
`+int not_equal(Coord c1, Coord c2) {`
`+    return !equal(c1, c2);`
`+}`
`+`
`+int set_room(Maze* m, int x, int y, int val) {`
`+    if (m != NULL && x < m->size.x && y < m->size.y) {`
`+        m->maze[x][y] = val;`
`+        return 1;`
`+    }`
`+    return 0;`
`+}`
`+`
`+int mark_here(Maze* m) {`
`+    if (!m) return ERROR;`
`+    return set_room(m, m->position.x, m->position.y, m->marker);`
`+}`
`+`
`+int move_to_start(Maze* m) {`
`+    if (!m) return ERROR;`
`+    m->position.x = 1;`
`+    m->position.y = 0;`
`+    return 1;`
`+}`
`+`
`+void load_maze(Maze* m, const char* filename) {`
`+    FILE * pFile;`
`+    int c;`
`+    int x = 0, y = 0;`
`+    pFile=fopen (filename,"r");`
`+    if (pFile==NULL) {`
`+        perror ("Error opening file");`
`+    } else {`
`+        do {`
`+            c = fgetc (pFile);`
`+            if (x >= MAX_MAZE_X || y >= MAX_MAZE_Y) {`
`+                printf("error: maximum number of rows or columns exceeded. max x=%d, max y=%d.\n", MAX_MAZE_X, MAX_MAZE_Y);`
`+                exit(1);`
`+            }`
`+            if (c == '\n') {`
`+                if (x > 0) {`
`+                    if (m->size.x > 0 && m->size.x != x + 1) {`
`+                        printf("error: Not all rows have the same length. check row %d.\n", y + 1);`
`+                        exit(1);`
`+                    } else {`
`+                        m->size.x = x + 1;`
`+                    }`
`+                    x = 0;`
`+                    ++y;`
`+                }`
`+            } else if (c == ',') {`
`+                ++x;`
`+            } else if (c == '0' || c == '1') {`
`+                m->maze[x][y]=c-'0';`
`+            }`
`+        } while (c != EOF);`
`+        m->size.y = y;`
`+        fclose (pFile);`
`+    }`
`+}`
`+`
`+void print_maze(Maze* m) {`
`+    int x, y;`
`+    `
`+    for (y = 0; y < m->size.y; ++y) {`
`+        for (x = 0; x < m->size.x; ++x) {`
`+            if (m->maze[x][y] > 0) {`
`+                printf("%d", m->maze[x][y]);`
`+            } else if (m->maze[x][y] == 0) {`
`+                printf(".");`
`+            } else {`
`+                printf("X");`
`+            }`
`+        }`
`+        printf("\n");`
`+    }`
`+}`
`+`
`+int try_move(Maze* m, Coord d) {`
`+    if (!m) return ERROR;`
`+    `
`+    Coord newPosition = add(m->position, d);`
`+    `
`+    if (newPosition.x < 0 || newPosition.x >= m->size.x ||`
`+        newPosition.y < 0 || newPosition.y >= m->size.y) {`
`+        return 0; // invalid position`
`+    }`
`+    `
`+    return m->maze[newPosition.x][newPosition.y];`
`+}`
`+`
`+int move(Maze* m, Coord d) {`
`+    if (!m) return ERROR;`
`+    `
`+    int success = 0;`
`+    Coord newPosition = add(m->position, d);`
`+    `
`+    if (try_move(m, d)) {`
`+        m->lastPosition = m->position;`
`+        m->position = newPosition;`
`+    `
`+        success = m->maze[m->lastPosition.x][m->lastPosition.y];`
`+        m->maze[m->position.x][m->position.y] = m->marker;`
`+    }`
`+    `
`+    return success;`
`+}`
`+`
`+int road_count(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    int i, sum, p;`
`+    `
`+    for (sum = 0, i = -1; i < 2; i+=2) {`
`+        p = m->position.x + i;`
`+        if (p >= 0 && p < m->size.x) {`
`+            sum+=(m->maze[p][m->position.y] != 0)?1:0;`
`+        }`
`+        p = m->position.y + i;`
`+        if (p >= 0 && p < m->size.y) {`
`+            sum+=(m->maze[m->position.x][p] != 0)?1:0;`
`+        }`
`+    }`
`+    `
`+    return sum;`
`+}`
`+`
`+int is_cross_roads(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    return road_count(m) > 2;`
`+}`
`+`
`+int is_dead_end(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    return road_count(m) <= 1;`
`+}`
`+`
`+int is_next_to_wall(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    if (m->position.x == 0 || m->position.x == m->size.x - 1 ||`
`+        m->position.y == 0 || m->position.y == m->size.y - 1) {`
`+        return 1;`
`+    }`
`+    `
`+    return 0;`
`+}`
`+`
`+// mark paths`
`+int solve_maze(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    int path_marker = 1;`
`+    int dead_end_path_marker = -1;`
`+    Coord direction;`
`+    int pathCost, lowestPathCost;`
`+    int isDeadEnd = 0;`
`+    `
`+    m->marker = path_marker;`
`+    mark_here(m);`
`+    move(m, down);`
`+    `
`+    while(!is_next_to_wall(m)) {`
`+        Coord back = sub(m->lastPosition, m->position);`
`+        if (is_cross_roads(m)) {`
`+            if (!isDeadEnd) {`
`+                m->marker = ++path_marker;`
`+                mark_here(m);`
`+            } else {`
`+                isDeadEnd = 0;`
`+                m->marker = --path_marker;`
`+                mark_here(m); // update this marker`
`+            }`
`+        } else if (is_dead_end(m)) {`
`+            isDeadEnd = 1;`
`+            m->marker = dead_end_path_marker;`
`+            mark_here(m);`
`+            move(m, back);`
`+            continue;`
`+        }`
`+        `
`+        lowestPathCost = pathCost = try_move(m, left);`
`+        if (not_equal(left, back) && pathCost > 0) {`
`+            direction = left;`
`+        }`
`+        pathCost = try_move(m, right);`
`+        if (not_equal(right, back) && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = right;`
`+            }`
`+        }`
`+        pathCost = try_move(m, up);`
`+        if (not_equal(up, back) && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = up;`
`+            }`
`+        }`
`+        pathCost = try_move(m, down);`
`+        if (not_equal(up, back) && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = down;`
`+            }`
`+        }`
`+        move(m, direction);`
`+    }`
`+    `
`+    return 1;`
`+}`
`+`
`+// Go to highest valued path at intersections`
`+int print_solution(Maze* m) {`
`+    if (!m) return ERROR;`
`+    `
`+    int path_marker = 1;`
`+    Coord direction;`
`+    int pathCost, highestPathCost;`
`+    `
`+    move_to_start(m);`
`+    m->marker = path_marker;`
`+    mark_here(m);`
`+    printf("Solution: (%d,%d)", m->position.x, m->position.y);`
`+    move(m, down);`
`+    `
`+    while(!is_next_to_wall(m)) {`
`+        Coord back = sub(m->lastPosition, m->position);`
`+        `
`+        highestPathCost = pathCost = try_move(m, left);`
`+        if (not_equal(left, back) && pathCost > 0) {`
`+            direction = left;`
`+        }`
`+        pathCost = try_move(m, right);`
`+        if (not_equal(right, back) && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = right;`
`+            }`
`+        }`
`+        pathCost = try_move(m, up);`
`+        if (not_equal(up, back) && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = up;`
`+            }`
`+        }`
`+        pathCost = try_move(m, down);`
`+        if (not_equal(down, back) && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = down;`
`+            }`
`+        }`
`+        `
`+        printf("(%d,%d)", m->position.x, m->position.y);`
`+        move(m, direction);`
`+    }`
`+    `
`+    printf("(%d,%d)\n", m->position.x, m->position.y);`
`+    printf("Exit at (%d, %d)\n", m->position.x, m->position.y);`
`+    `
`+    return 1;`
`+}`
`+`
`+int main() {`
`+    Maze maze;`
`+    `
`+    initialize_globals();`
`+`
`+    move_to_start(&maze);`
`+    load_maze(&maze, "maze.txt");`
`+    solve_maze(&maze);`
`+    print_solution(&maze);`
`+    `
`+    return 0;`
`+}`
`+`

`+MAZE SOLVER`
`+`
`+PROBLEM:`
`+========`
`+Write a C or C++ program to be a virtual maze walking mouse for a two dimensional maze of X columns and Y rows.`
`+int maze[x][y];`
`+maze[?][?] == 1 means empty corridor.`
`+maze[?][?] == 0 means solid wall.`
`+ `
`+The entry point is fixed from (1,0); (i.e. maze[1][0] will always be 1).`
`+The exit point is a 1 at the edge of the maze.`
`+The output of the program is a set of (x,y) coordinates that leads from entry (1,0) to (?,?) the exit.`
`+ `
`+Example:`
`+0,1,0,0,0,0,0,0,0,0,0`
`+0,1,1,1,1,1,1,0,0,0,0`
`+0,0,0,1,0,0,1,1,0,0,0`
`+0,0,1,1,0,0,1,0,0,0,0`
`+0,0,0,0,0,1,1,1,1,0,0`
`+0,0,1,1,1,1,0,0,1,0,0`
`+0,0,0,1,0,0,0,0,0,0,0`
`+Entry at (1,0)`
`+ `
`+Virtual mouse should print out below:`
`+Solution: (1,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(6,2)(6,3)(6,4)(5,4)(5,5)(4,5)(3,5)(3,6)`
`+Exit at (3,6)`
`+`
`+Instructions:`
`+·         Follow the K.I.S.S. concept.`
`+·         Readability first, performance next.(i.e. the more thinking needed to understand the code the lower the score).`
`+·         Minimum C++ approach (for readability and portability), keep it simple.(i.e. the more C++ specific expression the lower the score).`
`+·         Code should for the most part be self documenting.`
`+`
`+`
`+SOLUTION:`
`+=========`
`+The solver works by eliminating dead ends and is not optimized to find `
`+the shortest path (KISS requirement).`
`+`
`+There is a makefile included so run "make" to compile the program.`
`+`
`+The maze.txt file contains the assigned maze and will be loaded and solved each`
`+time the program is run. Alter it to test different mazes. Note, that the format`
`+of the file must remain "the same", i.e. there must be no comma at the end of a line, `
`+only 0's, 1's and ',' are allowed (though whitespace should be ignored this was not `
`+tested) and there must be a new line at the end of the file.`
`+`
`+Kind regards`
`+`
`+Lazar Sumar`

# File C++ Solution/main.cpp

`+/* Author: Lazar Sumar`
`+ * Date 27th March 2012`
`+ */`
`+#include "maze.h"`
`+#include "mouse.h"`
`+`
`+int main() {`
`+    Maze maze;`
`+    Mouse mouse;`
`+    `
`+    maze.load("maze.txt");`
`+    mouse.setMaze(&maze);`
`+    mouse.solveMaze();`
`+    mouse.printSolution();`
`+    return 0;`
`+}`

# File C++ Solution/makefile

`+CC=g++`
`+CFLAGS=-Wall`
`+LIB=`
`+EXEC=maze_solver`
`+`
`+\$(EXEC): main.cpp maze.o mouse.o`
`+	\$(CC) \$(CFLAGS) -o \$(EXEC) main.cpp maze.o mouse.o`
`+    `
`+maze.o: maze.h maze.cpp`
`+	\$(CC) \$(CFLAGS) -c maze.cpp`
`+`
`+mouse.o: mouse.h mouse.cpp`
`+	\$(CC) \$(CFLAGS) -c mouse.cpp`

# File C++ Solution/maze.cpp

`+#include "maze.h"`
`+#include <stdio.h>`
`+#include <stdlib.h>`
`+`
`+Coord left(-1, 0);`
`+Coord right(1, 0);`
`+Coord up(0, -1);`
`+Coord down(0, 1);`
`+`
`+`
`+Maze::Maze() {`
`+    position = Coord(1,0);`
`+    lastPosition = Coord(1,0);`
`+    marker = 1;`
`+}`
`+    `
`+void Maze::load(const char* filename) {`
`+    FILE * pFile;`
`+    int c;`
`+    int x = 0, y = 0;`
`+    pFile=fopen (filename,"r");`
`+    if (pFile==NULL) {`
`+        perror ("Error opening file");`
`+    } else {`
`+        do {`
`+            c = fgetc (pFile);`
`+            if (x >= MAX_MAZE_X || y >= MAX_MAZE_Y) {`
`+                printf("error: maximum number of rows or columns exceeded. max x=%d, max y=%d.\n", MAX_MAZE_X, MAX_MAZE_Y);`
`+                exit(1);`
`+            }`
`+            if (c == '\n') {`
`+                if (x > 0) {`
`+                    if (size.x > 0 && size.x != x + 1) {`
`+                        printf("error: Not all rows have the same length. check row %d.\n", y + 1);`
`+                        exit(1);`
`+                    } else {`
`+                        size.x = x + 1;`
`+                    }`
`+                    x = 0;`
`+                    ++y;`
`+                }`
`+            } else if (c == ',') {`
`+                ++x;`
`+            } else if (c == '0' || c == '1') {`
`+                maze[x][y]=c-'0';`
`+            }`
`+        } while (c != EOF);`
`+        size.y = y;`
`+        fclose (pFile);`
`+//        printf("Loaded %d x %d maze (rows x columns).\n", size.y, size.x);`
`+    }`
`+}`
`+`
`+void Maze::print() const {`
`+    int x, y;`
`+    `
`+    for (y = 0; y < size.y; ++y) {`
`+        for (x = 0; x < size.x; ++x) {`
`+            if (maze[x][y] > 0) {`
`+                printf("%d", maze[x][y]);`
`+            } else if (maze[x][y] == 0) {`
`+                printf(".");`
`+            } else {`
`+                printf("X");`
`+            }`
`+        }`
`+        printf("\n");`
`+    }`
`+}`
`+`
`+int Maze::setPathMarker(int marker) {`
`+    return this->marker = marker;`
`+}`
`+`
`+int Maze::tryMove(Coord d) const {`
`+    Coord newPosition = position + d;`
`+    if (newPosition.x < 0 || newPosition.x >= size.x ||`
`+        newPosition.y < 0 || newPosition.y >= size.y) {`
`+        return 0; // invalid position`
`+    }`
`+    return maze[newPosition.x][newPosition.y];`
`+}`
`+`
`+int Maze::move(Coord d) {`
`+    int success = 0;`
`+    Coord newPosition = position + d;`
`+    `
`+    if (tryMove(d)) {`
`+        lastPosition = position;`
`+        position = newPosition;`
`+    `
`+        success = maze[lastPosition.x][lastPosition.y];`
`+        maze[position.x][position.y] = marker;`
`+    }`
`+    `
`+    return success;`
`+}`
`+`
`+void Maze::moveToStart() {`
`+    position = Coord(1, 0);`
`+}`
`+`
`+void Maze::moveTo(Coord c) {`
`+    position = c;`
`+}`
`+`
`+void Maze::markPath() {`
`+    maze[position.x][position.y] = marker;`
`+}`
`+`
`+int Maze::roadCount() const {`
`+    int i, sum, p;`
`+    `
`+    for (sum = 0, i = -1; i < 2; i+=2) {`
`+        p = position.x + i;`
`+        if (p >= 0 && p < size.x) {`
`+            sum+=(maze[p][position.y] != 0)?1:0;`
`+        }`
`+        p = position.y + i;`
`+        if (p >= 0 && p < size.y) {`
`+            sum+=(maze[position.x][p] != 0)?1:0;`
`+        }`
`+    }`
`+    `
`+    return sum;`
`+}`
`+`
`+int Maze::isCrossRoads() const {`
`+    return roadCount() > 2;`
`+}`
`+`
`+int Maze::isDeadEnd() const {`
`+    return roadCount() <= 1;`
`+}`
`+`
`+Coord Maze::getSize() const {`
`+    return this->size;`
`+}`
`+`
`+Coord Maze::getPosition() const {`
`+    return this->position;`
`+}`
`+`
`+Coord Maze::getLastPosition() const {`
`+    return this->lastPosition;`
`+}`
`+`
`+int Maze::isNextToWall() const {`
`+    if (position.x == 0 || position.x == size.x - 1 ||`
`+        position.y == 0 || position.y == size.y - 1) {`
`+        return 1;`
`+    }`
`+    `
`+    return 0;`
`+}`

# File C++ Solution/maze.h

`+/* Author: Lazar Sumar`
`+ * Date 27th March 2012`
`+ */`
`+#ifndef MAZE_H`
`+#define MAZE_H`
`+`
`+#define MAX_MAZE_X 1000`
`+#define MAX_MAZE_Y 1000`
`+`
`+class Coord {`
`+public:`
`+    int x, y;`
`+`
`+    Coord(int x = 0, int y = 0) : x(x), y(y) {}`
`+    Coord(const Coord& c) : x(c.x), y(c.y) {}`
`+    `
`+    Coord& operator=(const Coord& c) {`
`+        x = c.x; y = c.y;`
`+        return *this;`
`+    }`
`+    `
`+    bool operator==(const Coord& c) const {`
`+        return x == c.x && y == c.y;`
`+    }`
`+    `
`+    bool operator!=(const Coord& c) const {`
`+        return !(*this == c);`
`+    }`
`+    `
`+    Coord operator-(const Coord& c) const {`
`+        return Coord(x - c.x, y - c.y);`
`+    }`
`+    `
`+    Coord operator+(const Coord& c) const {`
`+        return Coord(x + c.x, y + c.y);`
`+    }`
`+};`
`+`
`+typedef Coord Direction;`
`+`
`+extern Coord left;`
`+extern Coord right;`
`+extern Coord up;`
`+extern Coord down;`
`+`
`+class Maze {`
`+    int maze[MAX_MAZE_X][MAX_MAZE_Y];`
`+    Coord size;`
`+    Coord position;`
`+    int marker;`
`+    Coord lastPosition;`
`+    `
`+    int roadCount() const;`
`+public:`
`+    Maze();`
`+    `
`+    void load(const char* filename);`
`+    void print() const;`
`+    `
`+    int setPathMarker(int marker);`
`+    `
`+    int tryMove(Direction d) const;`
`+    int move(Direction d);`
`+    void moveToStart();`
`+    void moveTo(Coord c);`
`+    void markPath();`
`+    int isCrossRoads() const;`
`+    int isDeadEnd() const;`
`+    `
`+    Coord getSize() const;`
`+    Coord getPosition() const;`
`+    Coord getLastPosition() const;`
`+    `
`+    int isNextToWall() const;`
`+};`
`+`
`+#endif`

# File C++ Solution/maze.txt

`+0,1,0,0,0,0,0,0,0,0,0`
`+0,1,1,1,1,1,1,0,0,0,0`
`+0,0,0,1,0,0,1,1,0,0,0`
`+0,0,1,1,0,0,1,0,0,0,0`
`+0,0,0,0,0,1,1,1,1,0,0`
`+0,0,1,1,1,1,0,0,1,0,0`
`+0,0,0,1,0,0,0,0,0,0,0`

# File C++ Solution/mouse.cpp

`+/* Author: Lazar Sumar`
`+ * Date 27th March 2012`
`+ */`
`+#include "mouse.h"`
`+#include <stdio.h>`
`+`
`+Mouse::Mouse() {`
`+    maze = NULL;`
`+}`
`+`
`+void Mouse::setMaze(Maze* maze) {`
`+    this->maze = maze;`
`+}`
`+`
`+void Mouse::solveMaze() {`
`+    int path_marker = 1;`
`+    int dead_end_path_marker = -1;`
`+    Coord direction;`
`+    int pathCost, lowestPathCost;`
`+    int isDeadEnd = 0;`
`+    `
`+    maze->setPathMarker(path_marker);`
`+    maze->markPath();`
`+    maze->move(down);`
`+    `
`+    while(!maze->isNextToWall()) {`
`+        Coord back = maze->getLastPosition() - maze->getPosition();`
`+        if (maze->isCrossRoads()) {`
`+            if (!isDeadEnd) {`
`+                maze->setPathMarker(++path_marker);`
`+                maze->markPath();`
`+            } else {`
`+                isDeadEnd = 0;`
`+                maze->setPathMarker(--path_marker);`
`+                maze->markPath(); // update this marker`
`+            }`
`+        } else if (maze->isDeadEnd()) {`
`+            isDeadEnd = 1;`
`+            maze->setPathMarker(dead_end_path_marker);`
`+            maze->markPath();`
`+            maze->move(back);`
`+            continue;`
`+        }`
`+        `
`+        lowestPathCost = pathCost = maze->tryMove(left);`
`+        if (left != back && pathCost > 0) {`
`+            direction = left;`
`+        }`
`+        pathCost = maze->tryMove(right);`
`+        if (right != back && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = right;`
`+            }`
`+        }`
`+        pathCost = maze->tryMove(up);`
`+        if (up != back && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = up;`
`+            }`
`+        }`
`+        pathCost = maze->tryMove(down);`
`+        if (up != back && pathCost > 0) {`
`+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {`
`+                lowestPathCost = pathCost;`
`+                direction = down;`
`+            }`
`+        }`
`+        maze->move(direction);`
`+    }`
`+}`
`+`
`+void Mouse::printSolution() const {`
`+    int path_marker = 1;`
`+    Coord direction;`
`+    int pathCost, highestPathCost;`
`+    `
`+    maze->moveToStart();`
`+    maze->setPathMarker(path_marker);`
`+    maze->markPath();`
`+    printf("Solution: (%d,%d)", maze->getPosition().x, maze->getPosition().y);`
`+    maze->move(down);`
`+    `
`+    while(!maze->isNextToWall()) {`
`+        Coord back = maze->getLastPosition() - maze->getPosition();`
`+        `
`+        highestPathCost = pathCost = maze->tryMove(left);`
`+        if (left != back && pathCost > 0) {`
`+            direction = left;`
`+        }`
`+        pathCost = maze->tryMove(right);`
`+        if (right != back && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = right;`
`+            }`
`+        }`
`+        pathCost = maze->tryMove(up);`
`+        if (up != back && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = up;`
`+            }`
`+        }`
`+        pathCost = maze->tryMove(down);`
`+        if (down != back && pathCost > 0) {`
`+            if (highestPathCost < pathCost) {`
`+                highestPathCost = pathCost;`
`+                direction = down;`
`+            }`
`+        }`
`+        `
`+        printf("(%d,%d)", maze->getPosition().x, maze->getPosition().y);`
`+        maze->move(direction);`
`+    }`
`+    `
`+    Coord mazeExit = maze->getPosition();`
`+    printf("(%d,%d)\n", mazeExit.x, mazeExit.y);`
`+    printf("Exit at (%d, %d)\n", mazeExit.x, mazeExit.y);`
`+}`

# File C++ Solution/mouse.h

`+/* Author: Lazar Sumar`
`+ * Date 27th March 2012`
`+ */`
`+#ifndef MOUSE_H`
`+#define MOUSE_H`
`+`
`+#include "maze.h"`
`+#include <stdlib.h>`
`+`
`+class Mouse {`
`+    Maze* maze;`
`+public:`
`+    Mouse();`
`+    void setMaze(Maze* maze);`
`+    void solveMaze();`
`+    void printSolution() const;`
`+};`
`+`
`+#endif`