Leetcode 1091. Shortest Path in Binary Matrix | Leetcode daily Challenge | Breadth First Search Code

Показать описание

Use coupon ALISHA on any GeeksforGeeks course to get 10% discount:

Join this channel to get access to perks:

Check out our other playlists:

Dynamic Programming:
Trees:
Heaps and Maps:
Arrays and Maths:
Bit Manipulation:
Greedy Algorithms:
Sorting and Searching:
Strings:

Linked Lists:
Stack and Queues:
Two Pointers:
Graphs, BFS, DFS:
Backtracking:

Non- DSA playlists:
Probability:
SQL-Basic Join functions:
SQL-Basic Aggregate functions:

Рекомендации по теме

Комментарии

Code in C++ :
queue<pair<pair<int, int>, int>>q;
q.push({{0, 0}, 1});

if(grid[0][0]==1)return -1;

if(grid[0][0]==0 && grid.size()==1 && grid[0].size()==1)return 1;

vector<vector<bool>>visited(grid.size(), vector<bool>(grid.size(), false));
visited[0][0]=true;
while(!q.empty())
{
pair<int, int>p = q.front().first; //{0, 0}
int x = p.first; //0
int y= p.second; //0
int lengthOfPath = q.front().second; //1
q.pop();

vector<pair<int, int>>neighbours = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},
{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

for(pair<int, int>neighbour: neighbours)
{
int newx = neighbour.first + x;
int newy = neighbour.second+ y;

if(newx>=0 && newy>=0 && newx<grid.size() && newy<
grid[0].size() && grid[newx][newy]==0 &&
!visited[newx][newy])
{
q.push({{newx, newy}, lengthOfPath+1});
visited[newx][newy] = true;

if(newx==grid.size()-1 && newy==grid[0].size()
-1)return lengthOfPath+1;

}

}

}

return -1;

Use coupon ALISHA on any GeeksforGeeks course to get 10% discount:

probabilitycodingisfunis

Again a very beautiful explanation by Alisha, I tried solving this problem by using DFS, tried all possible ways to do it but couldn't get over ttl and stack overflow problem . Saw a few explanation with bfs but the codes were not explained properly finally found one of the best explanation ever. the way you dry run the logic is really very helpful Thanks 🙏🙏🙏🙏🤗🤗

manjitKK

very easy approach and explanation . thank you

NeerajBhardwaj

great explainatiion how u came to this approach

anniepatel

Your explaination skill is really amazing

dhainik.suthar

Mam your teaching style is very good . It will be good if u start a dsa playlist from beginning to advanced.

soumya

Great explanation Mam. Can this be solved using DFS ?

SomneelMaity

mam please also make a video on upcoming placement roadmap

amitraj-xsxm

mdm, i need to learn graphs, how do I learn it

Nitishkumar-rdjq

i have also do same thing but i got TLE problem does testcase upgraded plz check ??

physicslover

Very nice explanation, can you tell me can i do this problem by dp? How to recognize in such problems whether to go with bfs or dp?

amanbhadani

This is wrong, because BFS doesn't guarantee shortest path. The path could be of any length.

Shuvooa

Leetcode 1091. Shortest Path in Binary Matrix | Leetcode daily Challenge | Breadth First Search Code

Shortest Path in a Binary Matrix - Leetcode 1091 - Python

SHORTEST PATH IN A BINARY MATRIX | LEETCODE 1091 | PYTHON BFS SOLUTION

Shortest Path in Binary Matrix | Live Coding with Explanation | Leetcode - 1091

Shortest Path in Binary Matrix | Leetcode-1091 | Dijkstra in 2-D Matrix |Graph Concepts & Qns - ...

1091. Shortest Path in Binary Matrix - Day 1/30 Leetcode June Challenge

Leetcode 1091. Shortest Path in Binary Matrix | Leetcode daily Challenge | Breadth First Search Code

Shortest Path in Binary Matrix - Leetcode 1091 - Python

Shortest Path in Binary Matrix - LeetCode 1091 - JavaScript

Shortest Path in a Binary Matrix - LeetCode 1091 - Python

Shortest Path in Binary Matrix - LeetCode #1091 Python, JavaScript, Java and C++

1091. Shortest Path in Binary Matrix - Day 16/31 Leetcode May Challenge

Leetcode - Shortest Path in Binary Matrix (Python)

Shortest Path in Binary Matrix (Leetcode 1091)

1091. Shortest Path in Binary Matrix - Day 13/28 Leetcode February Challenge

Shortest Path in Binary Matrix || Leetcode 1091 || 2 Variant Questions Big Tech Actually Asks

Leetcode 1091. Shortest Path in Binary Matrix

[Java] Leetcode 1091. Shortest Path in Binary Matrix [Search #8]

G-36. Shortest Distance in a Binary Maze

LeetCode 1091: Shortest Path in Binary Matrix: Python Medium

Shortest Path In a Binary Matrix | Leetcode 1091 | BFS traversal

Leetcode 1091 Shortest Matrix Clear Path [C++] BFS

Google Coding Interview Question | Leetcode 1091 | Shortest Path in Binary Matrix

Conquer Python: BFS Mastery Through LeetCode Challenge 1091 - Shortest Path in Binary Matrix

LeetCode 1091. Shortest Path in Binary Matrix | JSer - JavaScript & Algorithm