# 6ms c++ dfs using stack

• I use stack to solve this problem. It works well. However, I think this code may have problems in some cases.

In general, I store the index in vector stones in pair.first and the last step distance in pair.second.

``````
class Solution {
public:
bool canCross(vector<int>& stones) {
int end=stones.size();
if(stones[1]!=1) return false;
if(end==2) return true;
stack<pair<int,int>> stk;
stk.push(make_pair(1,1));
while(!stk.empty()){
pair<int,int> p1=stk.top();
stk.pop();
for(int i=p1.first+1;i<end;i++){
if(stones[i]-stones[p1.first]>p1.second+1){
if(stones[i]>2*stones[p1.first]+10)   //use it to pass the corner case. eg,  1,2,3,4,5,6,7,8,....,1000,99999999,
// without this judgement, it will get TLE. Still, in some cases, it may have some problems.
//But it can be solve it by changing "if condition" using math .
return false;
break;
}
if(stones[i]-stones[p1.first]>=p1.second-1){
if(i==end-1) return true;
stk.push(make_pair(i,stones[i]-stones[p1.first]));
}
}
}
return false;

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.