wordpress的系统构成图,宁波seo怎么选,wordpress设置新页面,小程序开发公司价格表OD统一考试#xff08;C卷#xff09; 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
在一个机房中#xff0c;服务器的位置标识在n*m的整数矩阵网格中#xff0c;1表示单元格上有服务器#xff0c;0表示没有。如果两台服务器位于同一行或者同一列… OD统一考试C卷 分值 200分 题解 Java / Python / C 题目描述
在一个机房中服务器的位置标识在n*m的整数矩阵网格中1表示单元格上有服务器0表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置则认为它们之间可以组成一个局域网请你统计机房中最大的局域网包含的服务器个数。
输入描述
第一行输入两个正整数n和m0n,m100
之后为n*m的二维数组代表服务器信息
输出描述
最大局域网包含的服务器个数。
示例1
输入
2 2
1 0
1 1输出
3说明 [0][0]、[1][0]、[1][1] 三台服务器互相连接可以组成局域网。 题解 如果两台服务器位于同一行或者同一列中紧邻的位置其实就是处于上下左右的位置可以使用并查集对紧邻的位置进行合并然后再遍历找到服务器数量最大的并查集并查集写法此题没有DFS简单。 此题使用 DFS进行深搜搜索过后将位置的值从1变成0。 C
#includeiostream
#includevector
using namespace std;int dfs(vectorvectorint grid, int i, int j) {if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] 0) {return 0;}// 标记当前服务器已访问grid[i][j] 0;int cnt 1;// 向上、向下、向左、向右进行深度优先搜索cnt dfs(grid, i - 1, j);cnt dfs(grid, i 1, j);cnt dfs(grid, i, j - 1);cnt dfs(grid, i, j 1);return cnt;
}int main() {int m, n;cin m n;vectorvectorint grid(m, vectorint(n));for (int i 0; i m; i) {for (int j 0; j n; j) {cin grid[i][j];}}int maxServers 0;// 遍历整个矩阵for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {// 使用深度优先搜索统计每个局域网的服务器数量maxServers max(maxServers, dfs(grid, i, j));}}}cout maxServers endl;return 0;
}Java
import java.util.Scanner;public class Main {public static int dfs(int[][] grid, int i, int j) {if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) {return 0;}// 标记当前服务器已访问grid[i][j] 0;int cnt 1;// 向上、向下、向左、向右进行深度优先搜索cnt dfs(grid, i - 1, j);cnt dfs(grid, i 1, j);cnt dfs(grid, i, j - 1);cnt dfs(grid, i, j 1);return cnt;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int m scanner.nextInt();int n scanner.nextInt();int[][] grid new int[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {grid[i][j] scanner.nextInt();}}int maxServers 0;// 遍历整个矩阵for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {// 使用深度优先搜索统计每个局域网的服务器数量maxServers Math.max(maxServers, dfs(grid, i, j));}}}System.out.println(maxServers);}
}Python
def dfs(grid, i, j):if i 0 or i len(grid) or j 0 or j len(grid[0]) or grid[i][j] 0:return 0# 标记当前服务器已访问grid[i][j] 0cnt 1# 向上、向下、向左、向右进行深度优先搜索cnt dfs(grid, i - 1, j)cnt dfs(grid, i 1, j)cnt dfs(grid, i, j - 1)cnt dfs(grid, i, j 1)return cntdef main():m, n map(int, input().split())grid [list(map(int, input().split())) for _ in range(m)]maxServers 0# 遍历整个矩阵for i in range(m):for j in range(n):if grid[i][j] 1:# 使用深度优先搜索统计每个局域网的服务器数量maxServers max(maxServers, dfs(grid, i, j))print(maxServers)if __name__ __main__:main()
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
