Bob has just won a maze competition, where he was required to cover every cell in the maze. The maze is represented as an M × N matrix, and every cell in the maze is either a free cell, or a wall. The maze has exactly one free cell in its boundary, which Bob used to enter as well as exit the maze. The maze has no cycles or any free cell that is completely surrounded by walls. Bob used the following strategy to explore all the cells: at any cell, he would always face the direction he was travelling in, and if there was a free cell on the right, he would go there. If the right cell was a wall, he would move forward and if the forward cell was also a wall, he would go to the left cell. If all the three directions had walls, he would turn back.
After successfully winning the competition, Bob wants to rebuild the maze based on his memory. All he can remember is that he was facing East in the beginning, and the steps he had taken inside the maze. Each step is described by a single letter, where F stands for forward, L for left, R for right and B stands for turning back. Each letter not only describes the movement by one cell, but also about the change in orientation. He started and finished his journey at the single free cell in the maze’s boundary.
Solution: My approach to the problem is greedily finding all the points from starting refernce as x = 0 and y = 0,and then going through the possible directions by string s and storing them in visited map...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
string s;
cin >> s;
int x = 0,y = 0;
map<pair<int,int>,int>visited;
visited[{0,0}] = 1;
//start from left boundary..
int maxX = 0,maxY = 0;
int minX = INT_MAX,minY = INT_MAX;
pair<int,int> dir = {1,0};
for(int i = 0;i < s.size();i++){
if(s[i] == 'F'){
if(dir.first == 1){
x++;
}
else if(dir.second == 1){
y++;
}
else if(dir.first == -1){
x--;
}
else if(dir.second == -1){
y--;
}
if(!visited[{x,y}]){
visited[{x,y}] = 1;
}
}else if(s[i] == 'R'){
if(dir.first == 1){
y++;
dir = {0,1};
}
else if(dir.second == 1){
x--;
dir = {-1,0};
}
else if(dir.first == -1){
y--;
dir = {0,-1};
}
else if(dir.second == -1){
x++;
dir = {1,0};
}
if(!visited[{x,y}]){
visited[{x,y}] = 1;
}
}else if(s[i] == 'L'){
if(dir.first == 1){
y--;
dir = {0,-1};
}
else if(dir.second == 1){
x++;
dir = {1,0};
}
else if(dir.first == -1){
y++;
dir = {0,1};
}
else if(dir.second == -1){
x--;
dir = {-1,0};
}
if(!visited[{x,y}]){
visited[{x,y}] = 1;
}
}else{
if(dir.first == 1){
x--;
dir = {-1,0};
}
else if(dir.second == 1){
y--;
dir = {0,-1};
}
else if(dir.first == -1){
x++;
dir = {1,0};
}
else if(dir.second == -1){
y++;
dir = {0,1};
}
if(!visited[{x,y}]){
visited[{x,y}] = 1;
}
}
cout << x << y << endl;
maxX = max(x,maxX);
maxY = max(y,maxY);
}
int rows = maxY;
int cols = maxX;
cols += 2;
rows += 3;
cout << rows << cols << endl;
vector<string>grid(rows);
string temp(cols,'W');
for(int i = 0;i < rows;i++){
grid[i] = temp;
}
for(auto it:visited){
grid[it.first.second + 1][it.first.first] = 'A';
}
for(int i = 0;i < rows ;i++){
cout << grid[i] << endl;
}
return 0;
}Although some modification required to find the upper Y bounds as well , tell me any wrong in the approach or suggest me the best / optimal approach>>