SRM453.5 – MazeMaker

A graph breadth-first-search problem.
Since Jim is smart, he’ll always find the shortest bfs path to every cell. So, what we’ll do is find the cell with the maximum distance and place the exit there.
Caution!

• Input maze isn’t always a square.

C++ implementation:

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

#define PUSH(x, y, d) if (x > -1 && y > -1  && y < (*maze).size() && x < (*maze)[y].size()&& \
		(*maze)[y][x] == '.') { q.push((x) | ((y) << 8) | ((d) << 16)); (*maze)[y][x] = 'X'; }
#define N 64

class MazeMaker {
	int maxD;
	vector<string> *maze;
	vector<int> *dX, *dY;
	void bfs(int sX, int sY) {
		queue<int> q;
		PUSH(sX, sY, 0);
		while (q.size()) {
			int x = q.front() & 0xFF, y = (q.front() >> 8) & 0xFF, d = q.front() >> 16;
			maxD = max(d, maxD);
			q.pop();
			for (int i = 0; i < (*dX).size(); ++i)
				PUSH(x + (*dX)[i], y + (*dY)[i], d + 1);
		}
	}
public:
	int longestPath(vector<string> maze, int sX, int sY, vector<int> dX, vector<int> dY) {
		this->maze = &maze;
		this->dX = &dY;
		this->dY = &dX;
		this->maxD = -1;
		bfs(sY, sX);
		for (int i = 0; i < maze.size(); ++i)
			for (int j = 0; j < maze[i].size(); ++j)
				if (maze[i][j] == '.' && (maxD = -1))
					break;
		return maxD;
	}
};