Commit96e5944

authored

Merge pull requestneetcode-gh#3089 from KwFung7/feature/js-solution-934

Create 0934-shortest-bridge.js

2 parentsccabe8b +b1869e5 commit96e5944Copy full SHA for 96e5944

File tree

+70

-0

lines changed

+70

-0

lines changed

Lines changed: 70 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,70 @@`
	`1`	`+constDIRECTIONS=[[-1,0],[1,0],[0,-1],[0,1]];`
	`2`	`+`
	`3`	`+constshortestBridge=(grid)=>{`
	`4`	`+constrows=grid.length;`
	`5`	`+constcols=grid[0].length;`
	`6`	`+`
	`7`	`+letqueue=[];`
	`8`	`+`
	`9`	`+constexploreIslandDFS=(row,col)=>{`
	`10`	`+if(row<0\|\|row>=rows\|\|col<0\|\|col>=cols\|\|grid[row][col]!==1){`
	`11`	`+returnfalse;`
	`12`	`+}`
	`13`	`+`
	`14`	`+queue.push([row,col]);`
	`15`	`+grid[row][col]=2;`
	`16`	`+`
	`17`	`+exploreIslandDFS(row-1,col);`
	`18`	`+exploreIslandDFS(row+1,col);`
	`19`	`+exploreIslandDFS(row,col-1);`
	`20`	`+exploreIslandDFS(row,col+1);`
	`21`	`+`
	`22`	`+returntrue;`
	`23`	`+};`
	`24`	`+`
	`25`	`+constbuildBridgeBFS=()=>{`
	`26`	`+letdistance=-1;`
	`27`	`+letcurrentQueue=[];`
	`28`	`+`
	`29`	`+while(queue.length){`
	`30`	`+currentQueue=queue;`
	`31`	`+queue=[];`
	`32`	`+`
	`33`	`+for(let[row,col]ofcurrentQueue){`
	`34`	`+for(let[dx,dy]ofDIRECTIONS){`
	`35`	`+constnextRow=row+dx;`
	`36`	`+constnextCol=col+dy;`
	`37`	`+`
	`38`	`+if(`
	`39`	`+nextRow>=0&&`
	`40`	`+nextRow<rows&&`
	`41`	`+nextCol>=0&&`
	`42`	`+nextCol<cols&&`
	`43`	`+grid[nextRow][nextCol]!==2`
	`44`	`+){`
	`45`	`+if(grid[nextRow][nextCol]===1){`
	`46`	`+returndistance+1;`
	`47`	`+}`
	`48`	`+`
	`49`	`+queue.push([nextRow,nextCol]);`
	`50`	`+grid[nextRow][nextCol]=2;`
	`51`	`+}`
	`52`	`+}`
	`53`	`+}`
	`54`	`+`
	`55`	`+distance++;`
	`56`	`+}`
	`57`	`+`
	`58`	`+return-1;`
	`59`	`+};`
	`60`	`+`
	`61`	`+for(leti=0;i<rows;i++){`
	`62`	`+for(letj=0;j<cols;j++){`
	`63`	`+if(exploreIslandDFS(i,j)){`
	`64`	`+returnbuildBridgeBFS();`
	`65`	`+}`
	`66`	`+}`
	`67`	`+}`
	`68`	`+`
	`69`	`+return-1;`
	`70`	`+};`

Comments

(0)