SRM453 MazeMaker

Mike Mazemeister has recently built a large maze in his backyard. The j-th character of the i-th element of maze is ‘X’ if the square is an impassable bush; otherwise, it is a ‘.’. Mike wants his friend, Jumping Jim, to solve the maze. Jim will start in row startRow in column startCol.

Unlike typical maze solvers, Jim has the ability to jump through the maze, rather than simply walking. Jim’s possible moves are described in moveRow and moveCol. The i-th element corresponds to a move Jim can make in which his current row is changed by moveRow[i], and his current column is changed by moveCol[i]. For example, if moveRow = {1, 0, -1} and moveCol = {3, -2, 5}, Jim’s legal moves are (1,3), (0, -2), and (-1, 5). However, Jim cannot move outside the boundary of the maze, and he cannot land on an impassable bush.

Mike wants to make the maze impossible for Jim to exit, and can place the exit in any cell containing a ‘.’ in the maze. If this turns out to be impossible, then Mike wants to make Jim’s trip take as long as possible. Jim is smart, and he will always exit the maze in the minimum number of jumps that he can. Return the maximum number of jumps that Jim will make to exit the maze; if it is impossible for him to exit the maze, return -1 instead.

#include <string>
#include <vector>
#include <queue>
using namespace std;

class MazeMaker {
    public:
        int longestPath(vector <string> maze, int startRow, int startCol,
                        vector <int> moveRow, vector <int> moveCol)
    {
        int max = 0;
        int width = maze[0].size(),
            height = maze.size();
        int boad[50][50];

        for(int i = 0; i < height; i++)
            for (int j = 0; j < width; j++)
                board[i][j] = -1;
        
        board[startRow][startCol] = 0;
        queue<int> queueX;
        queue<int> queueY;
        queueX.push(startCol);
        queueY.push(startRow);

        while(queueX.size() > 0){
            int x = queueX.front(),
                y = queueY.front();
            queueX.pop(); queueY.pop();
            for(int i = 0; i < moveRow.size(); i++){
                int nextX = x + moveCol[i],
                    nextY = y + moveRow[i];
                
                if ( 0 <= nextX && nextX < width 
                    && 0 <= nextY && nextY < height
                    && board[nextY][nextX] == -1
                    && maze[nextY].substr(nextX,1) == '.'){
                        board[nextY][nextX] = board[y][x] + 1;
                        queueX.push(nextX);
                        queueY.push(nextY);
                    }
            }
        }
        for (int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if (maze[i].substr(j, 1) == "." && board[i][j] == -1)
                    return -1;
                max = std::max(max,board[i][j]);
            }
        }
        return max;
    }
}