Shortest Bridge || Graph theory
Вставка
- Опубліковано 25 сер 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our UA-cam page: / pepcoding
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Follow us on Pinterest: / _created
Follow us on Twitter: home
.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer
please zoom in the code section that would be great!
Cpp code with slight change(0's are also marked visited):
class Solution {
void dfs(int i, int j, vector &grid, vector &visited, int n, queue &q){
if(i=n || visited[i][j] || grid[i][j]==0) return;
visited[i][j] = true;
q.push({i,j});
int dir[]={0,1,0,-1,0};
for(int x=0; x
thanks a lot
Bhaiya please increase the font size
In BFS, while adding the next row and col in the queue. Also, mark it visited in the vis array. Otherwise, it is giving tle on leetcode.
Right before enqueing the new child pair, why not mark the current pair (parent) visited? I did, but my sol got accepted.
Count nodes within K-distance from all nodes in a set sir is question pr bhi video explaination bna dijiye
logic bohot sahi bataya bhai.
Hope you like the video.
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
this solution is efficient because this is give tle in leetcode
For better insight, visit nados.io, where you will get well curated content and career opportunities.
visited 0 ko bhi mark krna pdega na
yes , bcoz some testcases will fail on leetcode
kya galti hai bhai?
class Solution {
public:
vector vis;
queue q;
void dfs(vector& grid,int x,int y,int r,int c)
{
if(x=c||vis[x][y]==true||grid[x][y]==0)
{
return;
}
//grid[x][y]=0;
vis[x][y]=true;
q.push({x,y});
dfs(grid,x,y+1,r,c);
dfs(grid,x,y-1,r,c);
dfs(grid,x+1,y,r,c);
dfs(grid,x-1,y,r,c);
}
int shortestBridge(vector& grid)
{
int r=grid.size();
int c=grid[0].size();
//queueq;
//vectorvis;
//memset(vis,false,sizeof(vis));
vis.resize(r,vector(c,0));
// for(int i=0;i
Font size is too low
In as far as land possible you have initialised level = -1 but here level=0. Why so?
this solution is giving "Memory Limit exceeded" error on leetcode
same code gives tle on leetcode...
are vai thoda toh zoom karde yaar
code is not visible
For best experience visit on nados.pepcoding.com
@@Pepcoding 😂😂
Kuch dikha hi nai 😕
This is a very bad explanation to a simple problem had to learn it from leetcode
import java.util.*;
class Solution {
private void dfs(int i, int j, int[][] grid, boolean[][] visited, int n, Queue q) {
if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j] || grid[i][j] == 0)
return;
visited[i][j] = true;
q.offer(new int[] { i, j });
int[] dir = { 0, 1, 0, -1, 0 };
for (int x = 0; x < 4; x++) {
dfs(i + dir[x], j + dir[x + 1], grid, visited, n, q);
}
}
public int shortestBridge(int[][] grid) {
int n = grid.length;
boolean flag = false;
if (n == 0)
return 0;
boolean[][] visited = new boolean[n][n];
Queue q = new LinkedList();
for (int i = 0; i < n && !flag; i++) {
for (int j = 0; j < n && !flag; j++) {
if (grid[i][j] == 1) {
dfs(i, j, grid, visited, n, q);
flag = true;
}
}
}
int level = 0;
while (!q.isEmpty()) {
int sze = q.size();
while (sze-- > 0) {
int[] top = q.poll();
int i = top[0];
int j = top[1];
int[] dir = { 0, 1, 0, -1, 0 };
for (int x = 0; x < 4; x++) {
int nrow = i + dir[x];
int ncol = j + dir[x + 1];
if (nrow < 0 || ncol < 0 || nrow >= n || ncol >= n || visited[nrow][ncol])
continue;
if (grid[nrow][ncol] == 1)
return level;
visited[nrow][ncol] = true;
q.offer(new int[] { nrow, ncol });
}
}
level++;
}
return 0;
}
}