-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path0317-ShortestDistanceFromAllBuildings.cs
70 lines (60 loc) · 2.71 KB
/
0317-ShortestDistanceFromAllBuildings.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
//-----------------------------------------------------------------------------
// Runtime: 140ms
// Memory Usage: 27.6 MB
// Link: https://leetcode.com/submissions/detail/375114984/
//-----------------------------------------------------------------------------
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0317_ShortestDistanceFromAllBuildings
{
public int ShortestDistance(int[][] grid)
{
if (grid == null || grid[0].Length == 0) return 0;
var directions = new int[4][] { new int[2] { 1, 0 }, new int[2] { 0, 1 }, new int[2] { -1, 0 }, new int[2] { 0, -1 }, };
int N = grid.Length, M = grid[0].Length;
var distances = new int[N, M];
var reach = new int[N, M];
int buildingNum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (grid[i][j] == 1)
{
buildingNum++;
var queue = new Queue<(int r, int c)>();
queue.Enqueue((i, j));
var isVisited = new bool[N, M];
int distance = 1;
while (queue.Count > 0)
{
int size = queue.Count;
for (int q = 0; q < size; q++)
{
(int r, int c) = queue.Dequeue();
foreach (var dir in directions)
{
int nextRow = r + dir[0];
int nextCol = c + dir[1];
if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M &&
grid[nextRow][nextCol] == 0 && !isVisited[nextRow, nextCol])
{
distances[nextRow, nextCol] += distance;
reach[nextRow, nextCol]++;
isVisited[nextRow, nextCol] = true;
queue.Enqueue((nextRow, nextCol));
}
}
}
distance++;
}
}
var min = int.MaxValue;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (grid[i][j] == 0 && reach[i, j] == buildingNum)
min = Math.Min(min, distances[i, j]);
return min == int.MaxValue ? -1 : min;
}
}
}