Solution:
will use DSF strategy. Use a bool flag to represent the status of the ball, true for stop and false for moving. The reason for distinguishing these two is that once it stops, it can move all the directions (if OK); but once it moves, it can only goes one direction (recorded in the trace string) until hits on the wall. And once the ball hits on the wall, there will be a switch between stop and move. In order to avoid duplicates, a visit vector is used to trace the visiting status of the ball positions only when it stops. For the smallest path, we will trace the steps needed. Once find the steps needed are larger than the one that have already been found, the recursion can return since it is not necessary.
Code:
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
vector<string> ss;
string s;
vector<vector<bool>> visit(maze.size(), vector<bool>(maze.front().size(), true));
//label only when stop;
visit[ball[0]][ball[1]] = false;
int step = 0, l = 0;
bool flag = true;//stop;
findDSF(maze, ball[0], ball[1], hole, visit, s, ss, step, l, flag);
if(ss.empty()) return "impossible";
sort(ss.begin(), ss.end());
return ss[0];
}
private:
void findDSF(vector<vector<int>> &m, int x, int y, vector<int> &h, vector<vector<bool>> &v,
string s, vector<string> &ss, int step, int &l, bool flag){
if(ss.size()&&step>l) return;//if more step needed, can give up;
if(x==h[0] && y==h[1]){
if(ss.empty() || step == l){ ss.push_back(s); l = step;}
else{
if(step<l){ ss.clear(); ss.push_back(s); l = step;}
}
return;
}
if(flag){//ball stops now, and is going to move;
if(x-1>=0&&!m[x-1][y]&&v[x-1][y]){
flag = false;
if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
findDSF(m, x-1, y, h, v, s+'u', ss, step+1, l, flag);
v[x-1][y] = true;
flag = true;
}
if(x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
flag = false;
if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y]))
{flag = true;v[x+1][y] = false;}
findDSF(m, x+1, y, h, v, s+'d', ss, step+1, l, flag);
v[x+1][y] = true;
flag = true;
}
if(y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
flag = false;
if((y+1==m.front().size()-1)||(y+1<m.front().size()-1&&m[x][y+2]))
{flag=true;v[x][y+1]=false;}
findDSF(m, x, y+1, h, v, s+'r', ss, step+1, l, flag);
v[x][y+1] = true;
flag = true;
}
if(y-1>=0&&!m[x][y-1]&&v[x][y-1]){
flag = false;
if((y-1==0)||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
findDSF(m, x, y-1, h, v, s+'l', ss, step+1, l, flag);
v[x][y-1] = true;
flag = true;
}
}
else{//ball is moving, and it may stop when hits on the wall;
if(s.back()=='u'&&x-1>=0&&!m[x-1][y]&&v[x-1][y]){
if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
findDSF(m, x-1, y, h, v, s, ss, step+1, l, flag);
v[x-1][y] = true;
flag = false;
}
else if(s.back()=='d'&&x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y]))
{flag = true;v[x+1][y] = false;}
findDSF(m, x+1, y, h, v, s, ss, step+1, l, flag);
v[x+1][y] = true;
flag = false;
}
else if(s.back()=='r'&&y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
if(y+1==m.front().size()-1||(y+1<m.front().size()-1&&m[x][y+2]))
{flag = true;v[x][y+1]=false;}
findDSF(m, x, y+1, h, v, s, ss, step+1, l, flag);
v[x][y+1] = true;
flag = false;
}
else if(s.back() =='l'&&y-1>=0&&!m[x][y-1]&&v[x][y-1]){
if(y-1==0||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
findDSF(m, x, y-1, h, v, s, ss, step+1, l, flag);
v[x][y-1] = true;
flag = false;
}
else return;
}
}
};
The code length is too long for DSF, and it should be shorter if using BSF. But we need to trace the path and steps too. So we need some data structure to connect the positions with the steps and paths. Pair structure (pair<int, string> is chosen for step and path, and positions can be represented by a two dimensional array. So the data structure overall looks like this: vector<vector<pair<int, string>>>. The code below is based on BSF strategy.Code:
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
pair<int, string> dp[30][30];
int n=maze.size(), m=maze[0].size();
for(int i=0;i<n;i++)for(int j=0;j<m;j++) dp[i][j]=make_pair(10000000,"");
vector<int> dx={1, 0, 0, -1};
vector<int> dy={0, -1, 1, 0};
string c="dlru";
queue<pair<int,int>> q;
q.push(make_pair(ball[0],ball[1]));
dp[ball[0]][ball[1]]=make_pair(0,"");
while(q.size()){
pair<int, int> t=q.front();
q.pop();
for(int i=0;i<4;i++){
pair<int, int> now=t;
int v=0;
while(1){
if(now.first==hole[0]&&now.second==hole[1])break;
pair<int, int> next=make_pair(now.first+dx[i],now.second+dy[i]);
if(next.first<0||next.second<0||next.first>=n||next.second>=m)break;
if(maze[next.first][next.second]==1)break;
v++;
now=next;
}
pair<int, string>tt=make_pair(dp[t.first][t.second].first+v,dp[t.first][t.second].second+c[i]);
if(v&&dp[now.first][now.second]>tt){
dp[now.first][now.second]=tt;
q.push(now);
}
}
}
if(dp[hole[0]][hole[1]].first==10000000)return "impossible";
return dp[hole[0]][hole[1]].second;
}
};
No comments :
Post a Comment