Simple Level Order Traversal C++


#1

bool is_valid(int i,int j,vector &C){
int n = C.size();
int m = C[0].size();
if(i<0 || j<0 || i>=n || j>=m)return false;
return true;
}

int Solution::solve(int A, int B, vector &C){
int n = A;
int m = B;
int dr[] = {0,-1,0,1};
int dc[] = {-1,0,1,0};
deque<pair<int,int> > zero_q;
deque<pair<int,int> > one_q;
zero_q.push_back(make_pair(0,0));
int steps = 0;
while(true){
while(!zero_q.empty()){
int i = zero_q.front().first;
int j = zero_q.front().second;
if(i==n-1 && j==m-1)return steps;
zero_q.pop_front();
char curr = C[i][j];
C[i][j] = ‘.’; // is_visited = true;
if(curr==‘R’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
zero_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘L’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
zero_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘U’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
zero_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘D’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
zero_q.push_back({i+1,j});
}
}
}
steps++;
int siz = one_q.size();
while(siz–){
int i = one_q.front().first;
int j = one_q.front().second;
if(i==n-1 && j==m-1)return steps;
one_q.pop_front();
char curr = C[i][j];
C[i][j] = ‘.’; // is_visited = true;
if(curr==‘R’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
zero_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘L’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
zero_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘U’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
zero_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
one_q.push_back({i+1,j});
}
}
else if(curr==‘D’){
if(is_valid(i,j-1,C) && C[i][j-1]!=’.’){
one_q.push_back({i,j-1});
}
if(is_valid(i-1,j,C) && C[i-1][j]!=’.’){
one_q.push_back({i-1,j});
}
if(is_valid(i,j+1,C) && C[i][j+1]!=’.’){
one_q.push_back({i,j+1});
}
if(is_valid(i+1,j,C) && C[i+1][j]!=’.’){
zero_q.push_back({i+1,j});
}
}
}
}
}


#2

Pakka Simple? , Soch le vai ek baar!


#3

Mera haath dukh gya scorll karke aur tu simple bolra?? bsdk!