fmars
BAN USER- 1of 1 vote
AnswersGiven a start position and an target position on the grid. You can move up,down,left,right from one node to another adjacent one on the grid. However there are some walls on the grid that you cannot pass. Now find the shortest path from the start to the target.
- fmars in United States
(This is easy done by BFS)
Extend. If you can remove three walls, then what is the shortest path from start to the target. (I have no ideal except for enumerate all the possibility of three walls. It must be the silly solution.) Does anyone have any idea?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm
Simply use a prefix tree to implement and here is an C++ code
[code]
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
int count;
map<char,node*>child;
node():count(0){;}
};
void insert(node*p,string s){
p->count++;
if(s.empty())return;
if(p->child.count(s[0])==0)
p->child[s[0]]=new node();
insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
node*p=root;
for(int i=0;i<s.size();i++){
p=p->child[s[i]];
if(p->count==1)
return s.substr(0,i+1);
}
return s;
}
int main(){
vector<string>v;
v.push_back("bearcat");
v.push_back("bear");
node*root=new node();
for(int i=0;i<v.size();i++)
insert(root,v[i]);
for(int i=0;i<v.size();i++)
cout<<v[i]<<":"<<query(root,v[i])<<endl;
return 0;
}
[/code]
- fmars November 06, 2014Simply use a prefix tree to implement and here is an C++ code
[code]
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
int count;
map<char,node*>child;
node():count(0){;}
};
void insert(node*p,string s){
p->count++;
if(s.empty())return;
if(p->child.count(s[0])==0)
p->child[s[0]]=new node();
insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
node*p=root;
for(int i=0;i<s.size();i++){
p=p->child[s[i]];
if(p->count==1)
return s.substr(0,i+1);
}
return s;
}
int main(){
vector<string>v;
v.push_back("bearcat");
v.push_back("bear");
node*root=new node();
for(int i=0;i<v.size();i++)
insert(root,v[i]);
for(int i=0;i<v.size();i++)
cout<<v[i]<<":"<<query(root,v[i])<<endl;
return 0;
}
[/code]
- fmars November 06, 2014
Hope I can get a coding problem as simple as this one tomorrow
- fmars November 06, 2014