1267.统计参与通信的服务器

链接：1267.统计参与通信的服务器
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、计数、矩阵
简介：请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

题解 1 - cpp

• 编辑时间：2023-08-24
• 执行用时：40ms
• 内存消耗：21.36MB
• 编程语言：cpp
• 解法介绍：两次遍历。

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), mmap[250][250] = {0};
        pair<int, int> prev = make_pair(-1, -1);
        for (int i = 0; i < n; i++) {
            prev = make_pair(-1, -1);
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    if (prev.first == -1) prev = make_pair(i, j);
                    else {
                        mmap[prev.first][prev.second] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        for (int j = 0; j < m; j++) {
            prev = make_pair(-1, -1);
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    if (prev.first == -1) prev = make_pair(i, j);
                    else {
                        mmap[prev.first][prev.second] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (mmap[i][j]) res += 1;
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-08-24
• 执行用时：100ms
• 内存消耗：17.79MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        mmap = [[0 for _ in range(m)] for _ in range(n)]
        prev = (-1, -1)
        for i in range(n):
            prev = (-1, -1)
            for j in range(m):
                if grid[i][j] == 1:
                    if prev[0] == -1:
                        prev = (i, j)
                    else:
                        mmap[prev[0]][prev[1]] = True
                        mmap[i][j] = True
        for j in range(m):
            prev = (-1, -1)
            for i in range(n):
                if grid[i][j] == 1:
                    if prev[0] == -1:
                        prev = (i, j)
                    else:
                        mmap[prev[0]][prev[1]] = True
                        mmap[i][j] = True
        res = 0
        for i in range(n):
            for j in range(m):
                if mmap[i][j]:
                    res += 1
        return res

题解 3 - rust

• 编辑时间：2023-08-24
• 执行用时：8ms
• 内存消耗：2.26MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_servers(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut mmap = vec![vec![false; m]; n];
        let mut prev = (usize::MAX, usize::MAX);
        for i in 0..n {
            prev = (usize::MAX, usize::MAX);
            for j in 0..m {
                if grid[i][j] == 1 {
                    if prev.0 == usize::MAX {
                        prev = (i, j);
                    } else {
                        mmap[prev.0][prev.1] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        for j in 0..m {
            prev = (usize::MAX, usize::MAX);
            for i in 0..n {
                if grid[i][j] == 1 {
                    if prev.0 == usize::MAX {
                        prev = (i, j);
                    } else {
                        mmap[prev.0][prev.1] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        let mut res = 0;
        for i in 0..n {
            for j in 0..m {
                if mmap[i][j] {
                    res += 1;
                }
            }
        }
        res
    }
}