leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

shortest-bridge.dart (4131B)

      1 //Given a matrix of 1's and 0's where 1's are land and 0's are water
      2 //find the shortest bridge possible to connect the two islands in the matrix together.
      3 //To solve this I first iterated through the matrix and found the two islands. Then using
      4 //DFS I mapped them out and placed them in their respective matricies which store the
      5 //positions of each 1. I then used BFS on the first island to expand out from it to find the 
      6 //shortest possible distance from the first island to the second and returned that value.
      7 //Time: 504ms Beats: 100%
      8 //Memory: 176.4MB Beats: 100%
      9 class Solution {
     10   Set<String> found = {};
     11   Set<String> second_island_set = {};
     12   Set<String> searched = {};
     13   int shortestBridge(List<List<int>> grid) {
     14 
     15       List<List<int>> first_island = [];
     16       List<List<int>> second_island = [];
     17       for(int i = 0 ; i < grid.length ; ++i){
     18           for(int x = 0 ; x < grid[i].length ; ++x){
     19               if(grid[i][x] == 1 && !(found.contains(i.toString() + " " + x.toString()))){
     20                   if(first_island.length == 0){
     21                     explore(grid, [i, x], first_island);
     22                   }
     23                   else{
     24                     explore(grid, [i, x], second_island);
     25                     i = 10000000;
     26                     break;
     27                   }
     28               }
     29           }
     30       }
     31       List<List<int>> queue = [];
     32       //Iterate through the first list to initialize the BFS queue.
     33       for(int i = 0 ; i < first_island.length ; ++i){
     34           queue.add(first_island[i]);
     35       }
     36       //Create map of second island for faster searching
     37       for(int i = 0 ; i < second_island.length ; ++i){
     38           second_island_set.add(second_island[i][0].toString() + " " + second_island[i][1].toString());
     39       }
     40 
     41       bool done = false;
     42       int iteration = 0;
     43 
     44       while(queue.length != 0 && done == false){
     45           int init_queue = queue.length;
     46           for(int i = 0 ; i < init_queue ; ++i){
     47             List<int> current = queue[i];
     48             String curr_str = current[0].toString() + " " + current[1].toString();
     49             if(searched.contains(curr_str)){
     50                 continue;
     51             }
     52             searched.add(curr_str);
     53             String current_str = current[0].toString() + " " + current[1].toString();
     54             if(second_island_set.contains(current[0].toString() + " " + current[1].toString())){
     55                 done = true;
     56                 break;
     57             }
     58             if(current[0] > 0){
     59                 queue.add([current[0] - 1, current[1]]);
     60             }
     61             if(current[1] > 0){
     62                 queue.add([current[0], current[1] - 1]);
     63             }
     64             if(current[0] < grid.length - 1){
     65                 queue.add([current[0] + 1, current[1]]);
     66             }
     67             if(current[1] < grid[current[0]].length - 1){
     68                 queue.add([current[0], current[1] + 1]);
     69             }
     70           }
     71           if(done != true){
     72             queue = queue.sublist(init_queue);
     73             iteration += 1;
     74           }
     75       }
     76       return iteration - 1;
     77 
     78   }
     79 
     80   //DFS to explore the entire island that is at the position[0][1]. This places the island positions in 
     81   //the inputted island matrix and adds the values to the found set to help not search the same island
     82   //multiple times.
     83   void explore(List<List<int>> grid , List<int> position, List<List<int>> island){
     84       int currentx = position[0];
     85       int currenty = position[1];
     86       if(grid[currentx][currenty] != 1){
     87           return;
     88       }
     89       String position_str = currentx.toString() + " " + currenty.toString();
     90       if(found.contains(position_str)){
     91           return;
     92       }
     93       found.add(position_str);
     94       island.add([currentx , currenty]);
     95       if(currentx > 0){
     96           explore(grid, [currentx - 1, currenty], island);
     97       }
     98       if(currenty > 0){
     99           explore(grid, [currentx, currenty - 1], island);
    100       }
    101       if(currentx < grid.length - 1){
    102           explore(grid, [currentx + 1, currenty], island);
    103       }
    104       if(currenty < grid[currentx].length - 1){
    105           explore(grid, [currentx, currenty + 1], island);
    106       }
    107 
    108   }
    109 
    110 
    111 
    112 }