-
Notifications
You must be signed in to change notification settings - Fork 0
/
ShortestBridge.cs
150 lines (134 loc) · 5.51 KB
/
ShortestBridge.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net.Mime;
using System.Reflection.Metadata.Ecma335;
using System.Text;
using System.Threading.Tasks;
namespace MyLeetCodeJourney
{
/*
* Exercise 934:
* You are given an n x n binary matrix grid where 1 represents land and 0 represents water.
*
* An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.
*
* You may change 0's to 1's to connect the two islands to form one island.
*
* Return the smallest number of 0's you must flip to connect the two islands.
*/
internal class ShortestBridge
{
private Queue<Tuple<int, int>> placesQueue = new Queue<Tuple<int, int>>();
public ShortestBridge() { }
public int ShortestBridgeSolution(int[][] grid)
{
placesQueue.Clear();
//Iterate through grid until encountering an island
int islandRow = 0;
int islandCol = 0;
int rows = grid.Length;
int cols = grid[0].Length;
for(int row = 0; row < rows; row++)
{
for(int col = 0; col < cols; col++)
{
if (grid[col][row] == 1)
{
islandCol = col;
islandRow = row;
placesQueue.Enqueue(new Tuple<int, int>(islandCol, islandRow));
break;
}
}
}
//Initialize a matrix of visited places
bool[,] visited = new bool[cols, rows];
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
visited[col, row] = false;
}
}
visited[islandCol, islandRow] = true;
//Initialize a matrix of distances from first island.
int[,] distances = new int[cols, rows];
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
distances[col, row] = -1;
}
}
distances[islandCol, islandRow] = 0;
//Insert all island points into placesQueue
TraverseIsland(grid, islandRow, islandCol, distances, visited);
//Breadth-First Scanning the grid.
while(placesQueue.Count > 0)
{
Tuple<int, int> currentPlace = placesQueue.Dequeue();
int currentPlaceValue = grid[currentPlace.Item1][currentPlace.Item2];
int[] colMoves = { 1, 0, -1, 0 };
int[] rowMoves = { 0, 1, 0, -1 };
for (int moveIndex = 0; moveIndex < colMoves.Length; moveIndex++)
{
int colNeighbor = currentPlace.Item1 + colMoves[moveIndex];
int rowNeighbor = currentPlace.Item2 + rowMoves[moveIndex];
if (colNeighbor < 0 || colNeighbor >= grid.Length || rowNeighbor < 0 || rowNeighbor >= grid.Length)
{
continue;
}
if (visited[colNeighbor, rowNeighbor])
{
continue;
}
visited[colNeighbor, rowNeighbor] = true;
//It means that we met the second island, because we already traversed the first island
if (grid[colNeighbor][rowNeighbor] == 1)
{
return distances[currentPlace.Item1, currentPlace.Item2];
}
else
{
distances[colNeighbor, rowNeighbor] = distances[currentPlace.Item1, currentPlace.Item2] + 1;
}
placesQueue.Enqueue(new Tuple<int, int>(colNeighbor, rowNeighbor));
}
}
//In case we have not encountered the second island.
return -1;
}
/// <summary>
/// Traversing through the first island and updating distances, visited, and placesQuaue with initial values.
/// </summary>
/// <param name="grid"></param>
/// <param name="col"></param>
/// <param name="row"></param>
private void TraverseIsland(int[][] grid, int col, int row, int[,] distances, bool[,] visited)
{
int[] colMoves = { 1, 0, -1, 0 };
int[] rowMoves = { 0, 1, 0, -1 };
for (int moveIndex = 0; moveIndex < colMoves.Length; moveIndex++)
{
int colNeighbor = col + colMoves[moveIndex];
int rowNeighbor = row + rowMoves[moveIndex];
if (colNeighbor < 0 || colNeighbor >= grid.Length || rowNeighbor < 0 || rowNeighbor >= grid.Length)
{
continue;
}
if (visited[colNeighbor, rowNeighbor])
{
continue;
}
if (grid[colNeighbor][rowNeighbor] == 1)
{
distances[colNeighbor, rowNeighbor] = 0;
visited[colNeighbor, rowNeighbor] = true;
placesQueue.Enqueue(new Tuple<int, int>(colNeighbor, rowNeighbor));
TraverseIsland(grid, colNeighbor, rowNeighbor, distances, visited);
}
}
}
}
}