tanmay001
BAN USERSpace complexity: rowxcol is unavoidable as new matrix is needed. For simplicity, I am using row+2 x col+2 matrix as internal buffer. And output is generated from central part of rowxcol. In addition, I use similar size boolean matrix to track visited node.
So, space = O(rowXcol)
Time complexity: For every guard, BFS is performed. So, O(nrc) where n = number of gurads, r = rows, c = columns
struct cellNode{
pair<int, int> pos;
int depth;
};
void bfs(vector<string> & os, vector<vector<bool>> visited, int y, int x){
int rows = os.size()-2;
int cols = os[0].length()-2;
//cout << "DBG: row x col = " << rows << ", " << cols << endl;
vector<pair<int, int>> exp = {{0,-1},{0,1},{-1,0},{1,0}};
queue<cellNode> posQ;
cellNode cell;
cell.depth = 0;
cell.pos.first = y;
cell.pos.second = x;
posQ.push(cell);
visited[y][x] = true;
int i , j;
while(!posQ.empty()){
cellNode cell = posQ.front();
int y = cell.pos.first;
int x = cell.pos.second;
int d = cell.depth;
posQ.pop();
if(os[y][x]!='W' && os[y][x]!='G'){
if(os[y][x]=='O'){
os[y][x] = '0' + d;
}else{
int old = os[y][x] - '0';
if(old>d){
os[y][x] = '0' + d;
}
}
}
//cout << "DBG: current poped = " << y << ", " << x << endl;
for(int p = 0 ; p<exp.size(); ++p){
int i = exp[p].first;
int j = exp[p].second;
int posy = y+i, posx = x+j;
if(!visited[posy][posx] && os[posy][posx]!='W' && os[posy][posx]!='G' && posy!=0 && posx!=0 && posy!=(rows+1) && posx!=(cols+1)){
cellNode cell;
cell.pos.first = posy;
cell.pos.second = posx;
cell.depth = d + 1;
posQ.push(cell);
visited[posy][posx] = true;
}
}
}
}
vector<string> guardMatrix(vector<string> map){
int rows = map.size();
int cols = map[0].length();
string temp(cols+2,'W');
vector<string> os(rows+2, temp);
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
os[i+1][j+1] = map[i][j];
}
}
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='G'){
//cout << "DBG: gurad = " << i << ", " << j << endl;
vector<vector<bool>> visited(rows+2, vector<bool>(cols+2,false));
bfs(os, visited, i+1, j+1);
}
}
}
vector<string> result = map;
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='O')
result[i][j] = os[i+1][j+1];
}
}
return result;
}
int main(){
/*vector<string> map = {"WWWW",
"GOOO",
"OWWG",
"OWOO",};*/
/*vector<string> map = {"GOWWO",
"OWOOO",
"OOWWO",
"OOOOG"}; */
vector<string> map = {"OOGOW",
"OOOOO",
"OWGWO",
"OOOOO",
"GOWOO"};
vector<string> newMap = guardMatrix(map);
for(auto & s : newMap)
cout << s << endl;
}
Time complexity: O(n) --> Traverse tree two times: n + n
Space Complexity: O(n) --> recursive + columns : n + n
struct TreeNode{
int val;
TreeNode *right;
TreeNode *left;
TreeNode(int x): val(x), right(NULL), left(NULL){};
};
void getColumns(TreeNode *node, int & min, int &max , int cur){
if(node == NULL ) return;
if(cur < min) min = cur;
if(cur > max) max = cur;
getColumns(node->left, min, max, cur-1);
getColumns(node->left, min, max, cur+1);
}
void fillColumn(TreeNode *node, int col, vector<vector<int> > & colums){
if(node == NULL) return;
colums[col].push_back(node->val);
fillColumn(node->left, col-1, colums);
fillColumn(node->right, col+1, colums);
}
void printColumns(TreeNode *root){
int min= INT_MAX, max=INT_MIN;
getColumns(root, min, max, 0);
int numColumns = max - min + 1;
vector<vector<int> > colums;
vector<int> temp;
for(int i =0 ; i < numColumns ; ++i){
colums.push_back(temp);
}
fillColumn(root, -min, colums);
for(auto & c : colums){
for(auto & i : c)
cout << i << ", ";
}
cout << endl;
}
Time complexity: O(n*k); n is the size of string
Space comp: O(n) ; boolean array
Idea is simple to iterate through string and check if current block is damaged or not. If damaged then place rollar. Now, from that position to rollar end position, check if by placing another rollar, do we cover any new damaged region? To check new vs. old damaged region, I am maintaining boolean vector which gets set when rollar is placed.
- tanmay001 June 11, 2016