Google Interview Question
SDE-3sCountry: United States
Using DFS
#include <iostream>
#include <limits.h>
#include <algorithm>
#define ROW 2
#define COL 2
using namespace std;
int FindClosestGuardRecurr(char matrix[ROW][COL], int i, int j, bool visited[ROW][COL], int dist)
{
if(matrix[i][j] == 'G')
{
return dist;
}
int minDist = INT_MAX;
visited[i][j] = 1;
if(i > 0 && (matrix[i-1][j] == '.' || matrix[i-1][j] == 'G') && visited[i-1][j] == 0)
{
minDist = min(minDist, FindClosestGuardRecurr(matrix, i-1, j, visited, dist+1));
}
if(i < ROW-1 && (matrix[i+1][j] == '.' || matrix[i+1][j] == 'G') && visited[i+1][j] == 0)
{
minDist = min(minDist, FindClosestGuardRecurr(matrix, i+1, j, visited, dist+1));
}
if(j > 0 && (matrix[i][j-1] == '.' || matrix[i][j-1] == 'G') && visited[i][j-1] == 0)
{
minDist = min(minDist, FindClosestGuardRecurr(matrix, i, j-1, visited, dist+1));
}
if(j < COL-1 && (matrix[i][j+1] == '.' || matrix[i][j+1] == 'G') && visited[i][j+1] == 0)
{
minDist = min(minDist, FindClosestGuardRecurr(matrix, i, j+1, visited, dist+1));
}
visited[i][j] = 0;
return minDist;
}
int** FindClosestGuard(char matrix[ROW][COL])
{
bool visited[ROW][COL];
int** result = new int*[ROW];
for(int i=0; i<ROW; i++)
{
result[i] = new int[COL];
}
for(int i=0; i<ROW; i++)
{
for(int j=0; j<COL; j++)
{
visited[i][j] = 0;
}
}
for(int i=0; i<ROW; i++)
{
for(int j=0; j<COL; j++)
{
if(matrix[i][j] != '#')
{
result[i][j] = FindClosestGuardRecurr(matrix, i, j, visited, 0);
if(result[i][j] == INT_MAX)
{
result[i][j] = -1;
}
}
else
{
result[i][j] = -1;
}
}
}
return result;
}
int main() {
char a[ROW][COL];
for(int i=0; i<ROW; i++)
{
for(int j=0; j<COL; j++)
{
cin>>a[i][j];
}
}
int** result = FindClosestGuard(a);
for(int i=0; i<ROW; i++)
{
for(int j=0; j<COL; j++)
{
cout<<result[i][j]<<" ";
}
cout<<endl;
}
}
BFS.
- Alex December 05, 2017