Skip to content

2852. Sum of Remoteness of All Cells 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  long long sumRemoteness(vector<vector<int>>& grid) {
    const long long sum =
        accumulate(grid.begin(), grid.end(), 0LL,
                   [](long long subtotal, const vector<int>& row) {
      return subtotal + accumulate(row.begin(), row.end(), 0LL,
                                   [](long long subtotal, const int cell) {
        return subtotal + max(0, cell);
      });
    });

    long long ans = 0;

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] > 0) {
          const auto [count, componentSum] = dfs(grid, i, j);
          ans += (sum - componentSum) * count;
        }

    return ans;
  }

 private:
  const vector<int> dirs{0, 1, 0, -1, 0};

  // Returns (count, componentSum) of connected component containing (x, y).
  pair<int, long long> dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return {0, 0};
    if (grid[i][j] == -1)
      return {0, 0};

    int count = 1;
    long long componentSum = grid[i][j];
    grid[i][j] = -1;  // Mark as visited.;

    for (int k = 0; k < 4; ++k) {
      const int x = i + dirs[k];
      const int y = j + dirs[k + 1];
      const auto [nextCount, nextComponentSum] = dfs(grid, x, y);
      count += nextCount;
      componentSum += nextComponentSum;
    }

    return {count, componentSum};
  }
};

 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
class Solution {
  public long sumRemoteness(int[][] grid) {
    long ans = 0;
    long sum = 0;

    for (int[] row : grid)
      for (int cell : row)
        sum += Math.max(0, cell);

    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length; ++j)
        if (grid[i][j] > 0) {
          long[] res = dfs(grid, i, j);
          final long count = res[0];
          final long componentSum = res[1];
          ans += (sum - componentSum) * count;
        }

    return ans;
  }

  private static final int[] dirs = {0, 1, 0, -1, 0};

  // Returns [count, componentSum] of connected component containing (x, y).
  private long[] dfs(int[][] grid, int i, int j) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return new long[] {0, 0};
    if (grid[i][j] == -1)
      return new long[] {0, 0};

    long count = 1;
    long componentSum = grid[i][j];
    grid[i][j] = -1; // Mark as visited.;

    for (int k = 0; k < 4; ++k) {
      final int x = i + dirs[k];
      final int y = j + dirs[k + 1];
      long[] nextRes = dfs(grid, x, y);
      final long nextCount = nextRes[0];
      final long nextComponentSum = nextRes[1];
      count += nextCount;
      componentSum += nextComponentSum;
    }

    return new long[] {count, componentSum};
  }
}

 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
class Solution:
  def sumRemoteness(self, grid: List[List[int]]) -> int:
    n = len(grid)
    dirs = [0, 1, 0, -1, 0]
    summ = sum(max(0, cell) for row in grid for cell in row)
    ans = 0

    def dfs(i: int, j: int) -> Tuple[int, int]:
      if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
        return (0, 0)
      if grid[i][j] == -1:
        return (0, 0)

      count = 1
      componentSum = grid[i][j]
      grid[i][j] = -1  # Mark as visited.

      for k in range(4):
        x = i + dirs[k]
        y = j + dirs[k + 1]
        nextCount, nextComponentSum = dfs(x, y)
        count += nextCount
        componentSum += nextComponentSum

      return (count, componentSum)

    for i in range(n):
      for j in range(n):
        if grid[i][j] > 0:
          count, componentSum = dfs(i, j)
          ans += (summ - componentSum) * count

    return ans