** I am sharing three code in second code and third
I am getting TLE ,Where as 1st got Accepted
i want to know is There only diff in Space complexity in approach 2nd and why including isvalid() in approah 3 gives TLE is there anything that i am missing
which makes 2nd and 3rd approach inefficent.
ProblemLink ---
https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/
ThankYou !!
**
Approach 1
class Solution
{
public:
int nearestExit(vector<vector<char>> &maze, vector<int> &entrance)
{
int m = maze.size();
int n = maze[0].size();
queue<pair<int, pair<int, int>>> q;
int posx[] = {-1, 1, 0, 0};
int posy[] = {0, 0, -1, 1};
bool visted[m][n];
memset(visted, false, sizeof visted);
q.push({0, {entrance[0], entrance[1]}});
maze[entrance[0]][entrance[1]] = '+';
while (!q.empty())
{
auto x = q.front();
int step = x.first;
q.pop();
if ((x.second.first == 0 || x.second.first == m - 1 || x.second.second == 0 || x.second.second == n - 1) && (x.second.first != entrance[0] || x.second.second != entrance[1]))
{
return x.first;
}
for (int i = 0; i < 4; i++)
{
int sx = x.second.first + posx[i];
int sy = x.second.second + posy[i];
if (sx >= 0 && sx < m && sy >= 0 && sy < n && maze[sx][sy] != '+')
{
q.push({step + 1, {sx, sy}});
maze[sx][sy] = '+';
}
}
}
return -1;
}
};
Approach 2
class Solution {
public:
bool isvalid(int sx, int sy, int m , int n, vector<vector<char>>maze ) {
return (sx>=0 && sx<m && sy>=0 && sy<n && maze[sx][sy]!='+');
}
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m= maze.size();
int n= maze[0].size();
queue<pair<int,pair<int,int>>>q;
int posx[]= {-1, 1, 0,0};
int posy[]={0,0,-1, 1};
bool visted[m][n];
memset(visted, false, sizeof visted);
q.push({0,{entrance[0], entrance[1]}});
visted[ entrance[0]][entrance[1]] = true;
while(!q.empty()) {
auto x= q.front();
int step= x.first;
q.pop();
if((x.second.first==0 || x.second.first == m-1 || x.second.second==0 || x.second.second==n-1) && (x.second.first != entrance[0] || x.second.second!=entrance[1])) {
return x.first;
}
for(int i=0; i<4; i++){
int sx= x.second.first+ posx[i];
int sy = x.second.second + posy[i];
if( isvalid(sx,sy,m,n , maze) && !visted[sx][sy]) {
q.push({step+1, {sx, sy}});
visted[sx][sy]=true;
}
}
}
return -1;
}
};
'''
Approach 3--
class Solution
{
public:
bool isvalid(int sx, int sy, int m, int n, vector<vector> maze)
{
return (sx >= 0 && sx < m && sy >= 0 && sy < n && maze[sx][sy] != '+');
}
int nearestExit(vector<vector<char>> &maze, vector<int> &entrance)
{
int m = maze.size();
int n = maze[0].size();
queue<pair<int, pair<int, int>>> q;
int posx[] = {-1, 1, 0, 0};
int posy[] = {0, 0, -1, 1};
q.push({0, {entrance[0], entrance[1]}});
maze[entrance[0]][entrance[1]] = '+';
while (!q.empty())
{
auto x = q.front();
int step = x.first;
q.pop();
if ((x.second.first == 0 || x.second.first == m - 1 || x.second.second == 0 || x.second.second == n - 1) && (x.second.first != entrance[0] || x.second.second != entrance[1]))
{
return x.first;
}
for (int i = 0; i < 4; i++)
{
int sx = x.second.first + posx[i];
int sy = x.second.second + posy[i];
if (isvalid(sx, sy, m, n, maze))
{
q.push({step + 1, {sx, sy}});
maze[sx][sy] = '+';
}
}
}
return -1;
}
};Comments (0)
