class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
def find(x):
if dc[x] != x: dc[x] = find(dc[x])
return dc[x]
m, n, POS, sm, res = len(grid), len(grid[0]), ((0, -1), (-1, 0)), 0, 0
has, dc = [-1] * (m*n), [-1] * (m*n)
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
sm, x = sm + grid[i][j], i*n+j
dc[x], has[x] = x, grid[i][j]
for dx, dy in POS:
nx, ny = i + dx, j + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
y = find(nx*n+ny)
if x != y: dc[y], has[x] = x, has[x] + has[y]
for i in range(m*n): res += (sm - has[find(i)]) if grid[i//n][i%n] > 0 else 0
return res
from collections import deque
class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
row = len(grid)
col = len(grid[0])
total_visited = set()
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
total_sum = 0
lst = []
for i in range(row):
for j in range(col):
if grid[i][j] > -1 and (i, j) not in total_visited:
queue = deque([(i, j)])
visited = {(i, j)}
while queue:
cur_i, cur_j = queue.popleft()
for di, dj in directions:
nxt_i, nxt_j = cur_i + di, cur_j + dj
if not (0 <= nxt_i < row and 0 <= nxt_j < col):
continue
if (nxt_i, nxt_j) in visited or grid[nxt_i][nxt_j] == -1:
continue
visited.add((nxt_i, nxt_j))
queue.append((nxt_i, nxt_j))
s = 0
for ii, jj in visited:
s += grid[ii][jj]
total_visited.add((ii, jj))
total_sum += s
lst.append([len(visited), s])
ans = 0
for count, s in lst:
ans += count * (total_sum - s)
return ans
func sumRemoteness(grid [][]int) int64 {
ans := 0
dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
n := len(grid)
cnt := 0
for i := range grid {
for j := range grid[i] {
if grid[i][j] != -1 {
cnt++
}
}
}
var dfs func(i, j int) (s, c int)
dfs = func(i, j int) (s, c int) {
if i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == -1 {
return 0, 0
}
s += grid[i][j]
c++
grid[i][j] = -1
for _, d := range dirs {
x, y := i + d[0], j + d[1]
t1, t2 := dfs(x, y)
s += t1
c += t2
}
return s, c
}
for i := range grid {
for j := range grid[i] {
if grid[i][j] != -1 {
s, c := dfs(i, j)
ans += s * (cnt - c)
}
}
}
return int64(ans)
}
class setUnion:
def __init__(self, size):
self.parent = list(range(size))
self.rank=[1]*size
self.setCount=size
def find(self,i):
if self.parent[i]==i:
return i
else:
self.parent[i]=self.find(self.parent[i])
return self.parent[i]
def union(self,i,j):
x,y=self.find(i),self.find(j)
if x==y:
return
if self.rank[x]<self.rank[y]:
x,y=y,x
self.rank[x]+=self.rank[y]
self.parent[y]=x
self.setCount-=1
def is_connected(self,i,j):
return self.find(i)==self.find(j)
def get_partset(self):
part=defaultdict(list)
for i in range(len(self.parent)):
part[self.find(i)].append(i)
return part
class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
n=len(grid)
size,total=n*n,0
kkk=setUnion(size)
for i in range(n):
for j in range(n):
if grid[i][j]>0:
for a,b in [(-1,0),(0,-1)]:
cur_i,cur_j=i+a,j+b
if cur_i<0 or cur_j<0 or grid[cur_i][cur_j]==-1:
continue
kkk.union(i*n+j,cur_i*n+cur_j)
total+=grid[i][j]
x=defaultdict(int)
for i in range(n):
for j in range(n):
if grid[i][j]>0:
x[kkk.find(i*n+j)]+=grid[i][j]
ans=0
for i in range(n):
for j in range(n):
if grid[i][j]>0:
ans+=total-x[kkk.find(i*n+j)]
return ans
