marinalepi
BAN USER- 1of 1 vote
AnswersCreate a maze.
- marinalepi in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 0of 0 votes
AnswersPlay Scrabble. You have 7 letters to start from. Build the word with the highest score.
- marinalepi in United States| Report Duplicate | Flag | PURGE
Google Software Engineer String Manipulation
#define LEFT 0
#define RIGHT 1
#define TOP 2
#define BOTTOM 3
struct coord {
int i, j;
};
void canMove(coord &next, vector<vector<int> > a, int i, int j) {
next.i = -1;
// out of boundaries
if (i < 0 || i >= a.size() || j < 0 || j >= a[0].size()) {
return;
}
// not the first or last square
if ((i = 0 && j == 0) || (i == a.size()-1 && j == a[0].size()-1)) {
return;
}
// if that cell is already taken
if (a[i][j] == 1) {
return;
}
// can't put the wall here, neighboor
if (a[i][j] == -1) {
return;
}
next.i = i;
next.j = i;
}
int selectNextMove(array<coord, 4> next) {
int startIndex = rand() % 4;
int index = startIndex;
for (;;) {
if (next[index].i != -1) {
return index;
}
index++;
if (index == startIndex) {
break;
}
if (index == 4) {
index = 0;
}
}
}
void buildMaze(vector<vector<int> > a) {
size_t i, j;
for (i = 0; i < a.size(); i++) {
for (j = 0; j < a.size(); j++) {
a[i][j] = 0;
}
}
array<coord, 4> next;
for (;;) {
canMove(next[LEFT], a, i, j-1);
canMove(next[RIGHT], a, i, j+1);
canMove(next[TOP], a, i-1, j);
canMove(next[BOTTOM], a, i+1, j);
int nextMove = selectNextMove(next);
if (nextMove == -1) { // can't move anywhere, break
break;
}
i = next[nextMove].i;
j = next[nextMove].j;
for (int dir=0; dir<4; dir++) {
if (next[dir].i != -1 && nextMove != dir) {
a[next[dir].i][next[dir].j] = -1;
}
}
}
// cleaning
for (i = 0; i < a.size(); i++) {
for (j = 0; j < a.size(); j++) {
if (a[i][j] == -1) {
a[i][j] = 0;
}
}
}
}
- marinalepi March 06, 2015