|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。
- 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。
- 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
-  
- 示例 1:
- 输入:grid = [[1,0],[0,1]]
- 输出:0
- 解释:没有一台服务器能与其他服务器进行通信。
- 示例 2:
- 输入:grid = [[1,0],[1,1]]
- 输出:3
- 解释:所有这些服务器都至少可以与一台别的服务器进行通信。
- 示例 3:
- 输入:grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
- 输出:4
- 解释:第一行的两台服务器互相通信,第三列的两台服务器互相通信,但右下角的服务器无法与其他服务器通信。
-  
- 提示:
- m == grid.length
- n == grid[i].length
- 1 <= m <= 250
- 1 <= n <= 250
- grid[i][j] == 0 or 1
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/count-servers-that-communicate
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- bool find_row(vector<vector<int> > & grid, int x, int y){
- for(int i = 0; i < grid[0].size(); i++){
- if(i != y && grid[x][i] == 1) return true;
- }
- return false;
- }
- bool find_col(vector<vector<int> > & grid, int x, int y){
- for(int j = 0; j < grid.size(); j++){
- if(j != x && grid[j][y] == 1) return true;
- }
- return false;
- }
- int countServers(vector<vector<int>>& grid) {
- //针对各位1的单元格查看其行列上是否有除其以为的1
- int res = 0;
- int len1 = grid.size(), len2 = grid[0].size();
- for(int i = 0; i < len1; i++){
- for(int j = 0; j < len2; j++){
- if(grid[i][j] == 1){
- if(find_row(grid, i, j) || find_col(grid, i, j)) res++;
- }
- }
- }
- return res;
- }
- };
复制代码
注意事项:
1.深度优先搜索失败,可能存在不连续却在同行同列的数据。 |
|