服务器连成局域网（华为od机考题）_业界新闻

发布时间:2024-08-08 07:07

阅读量:0

一、题目

1.原题

在一个机房中，服务器的位置标识在 n*m 的整数矩阵网格中，1 表示单元格上有服务器，0 表示没有。
如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网。
请你统计机房中最大的局域网包含的服务器个数。

二、思路与代码过程

1.思路

输入n和m的大小，然后输入全是0和1的整数矩阵。

找到所有1的位置存入list，比较所有节点位置确认相邻关系（fX，bX，uY，dY），存入LinkedXY链表中，（xstack和ystack没啥实际作用，只是思维过程中的一个思路，可以删掉）。

把LinkedXY中的所有点遍历放入LinkNodejoin函数中，每一个节点都向四周查找能抵达的最多节点数，最后全部遍历完返回最大值。

LinkNodejoin函数中，每一次循环countStack都会刷新传入，在内循环中继承，每个节点都会对其相邻节点进行递归查找，直到达到LinkedXY的最后一个节点（结束条件存在问题，需要优化）。

2.代码过程

①main函数

public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         System.out.println("请输入n和m的大小：");         int n = sc.nextInt();         int m = sc.nextInt();         System.out.println("请依次输入矩阵网格的值：");         int[][] matrix = new int[n][m];         for (int i = 0; i < n; i++) {             for (int j = 0; j < m; j++) {                 matrix[i][j] = sc.nextInt();             }         }         SearchMax(matrix,n,m);     }

②SearchMax函数

private static void SearchMax(int[][] matrix, int n, int m) {         Stack<int[]> xstack = new Stack<>();//         Stack<int[]> ystack = new Stack<>();//         ArrayList<int []> list = new ArrayList<>();         ArrayList<LinkNode> LinkedXY = new ArrayList<>();//=============         //把所有有服务器的位置都找到，存入list         for (int i = 0; i < n; i++) {             for (int j = 0; j < m; j++) {                 if (matrix[i][j] == 1) {                     list.add(new int[]{i, j});                 }             }         }         if (list.size()==0) {             System.out.println("当前矩阵无服务器。");         }         //System.out.println(Arrays.deepToString(list.toArray()));         //无遗漏比较01 02 03 12 13 23         LinkNode xnode1 = null;         LinkNode xnode2 = null;         LinkNode ynode1 = null;         LinkNode ynode2 = null;         for (int i = 0; i < list.size(); i++) {             for (int j = i+1; j < list.size(); j++) {                 xnode1 = new LinkNode(list.get(i)[0],list.get(i)[1]);                 xnode2 = new LinkNode(list.get(j)[0],list.get(j)[1]);                 ynode1 = new LinkNode(list.get(i)[0],list.get(i)[1]);                 ynode2 = new LinkNode(list.get(j)[0],list.get(j)[1]);                  if (list.get(i)[0] == list.get(j)[0]&&Math.abs(list.get(i)[1]-list.get(j)[1])==1) {                                  boolean exist1 = false;                     boolean exist2 = false;                     for ( LinkNode currentNode : LinkedXY) {                         if (currentNode.getX()==xnode1.getX() && currentNode.getY()==xnode1.getY()){                             exist1 = true;                             xnode1=currentNode;                         }                         if (currentNode.getX()==xnode2.getX() && currentNode.getY()==xnode2.getY()){                             exist2 = true;                             xnode2=currentNode;                             break;                         }                     }                     if (!exist1) {                         LinkedXY.add(xnode1);                     }                     if (!exist2) {                         LinkedXY.add(xnode2);                     }                     //有相邻入栈                     xstack.push(list.get(i));                     //若xnode1横坐标与xnode2相等，纵坐标小于xnode2，则将xnode2设为xnode1的后方                     //setbXlink                     if(list.get(i)[1]<list.get(j)[1]) {                         xnode1.setbXlink(xnode2);                         xnode2.setfXlink(xnode1);                     }                     //若xnode1横坐标与xnode2相等，纵坐标大于xnode2，则将xnode2设为xnode1的前方                     //setfXlink                     else if(list.get(i)[1]>list.get(j)[1]) {                         xnode1.setfXlink(xnode2);                         xnode2.setbXlink(xnode1);                     }                     //将相邻数入栈                     xstack.push(list.get(j));                 } else if (list.get(i)[1] == list.get(j)[1]&&Math.abs(list.get(i)[0]-list.get(j)[0])==1) {                                          boolean exist1 = false;                     boolean exist2 = false;                     for ( LinkNode currentNode : LinkedXY) {                         if (currentNode.getX()==ynode1.getX() && currentNode.getY()==ynode1.getY()){                             exist1 = true;                             ynode1=currentNode;                         }                         if (currentNode.getX()==ynode2.getX() && currentNode.getY()==ynode2.getY()){                             exist2 = true;                             ynode2=currentNode;                             break;                         }                     }                     if (!exist1) {                         LinkedXY.add(ynode1);                     }                     if (!exist2) {                         LinkedXY.add(ynode2);                     }                     //有相邻入栈                     ystack.push(list.get(i));                     //若xnode1纵坐标与xnode2相等，横坐标大于xnode2，则将xnode2设为xnode1的上方                     //setuYlink                     if(list.get(i)[0]>list.get(j)[0]) {                         ynode1.setuYlink(ynode2);                     }                     //若xnode1纵坐标与xnode2相等，横坐标小于xnode2，则将xnode2设为xnode1的下方                     //setdYlink                     else if(list.get(i)[0]<list.get(j)[0]) {                         ynode1.setdYlink(ynode2);                     }                     //将相邻数入栈                     ystack.push(list.get(j));                 }             }         }         if (xstack.isEmpty()&& ystack.isEmpty()){             System.out.println("无相邻服务器，最大局域网含1个服务器。");         }         int MaxSize = 0 ;         for (int i = 0; i < LinkedXY.size(); i++) {             Stack<LinkNode> countStack = new Stack<>();             LinkNodejoin(LinkedXY,LinkedXY.get(i),countStack);             MaxSize = Math.max(MaxSize,LinkNodejoin(LinkedXY,LinkedXY.get(i), countStack));         }         System.out.println("最大长度为："+MaxSize);     }

③ LinkNodejoin函数

private static int LinkNodejoin(ArrayList<LinkNode> LinkedXY,LinkNode CountcurrentNode, Stack<LinkNode> countStack) {         //当前countStack不含有之前已经存入的节点         if (!countStack.contains(CountcurrentNode)){             System.out.println("当前countStack不含有该节点，加入进来啦！");             countStack.push(CountcurrentNode);         }         if (CountcurrentNode==LinkedXY.get(LinkedXY.size()-1)){             return countStack.size();         }             if (CountcurrentNode.fxlink!=null&&!countStack.contains(CountcurrentNode.fxlink)){                 LinkNodejoin(LinkedXY, CountcurrentNode.getfXlink(),countStack);             }             if (CountcurrentNode.bxlink!=null&&!countStack.contains(CountcurrentNode.bxlink)){                 LinkNodejoin(LinkedXY, CountcurrentNode.getbXlink(),countStack);             }             if (CountcurrentNode.uylink!=null&&!countStack.contains(CountcurrentNode.uylink)){                 LinkNodejoin(LinkedXY, CountcurrentNode.getuYlink(),countStack);             }             if (CountcurrentNode.dylink!=null&&!countStack.contains(CountcurrentNode.dylink)){                 LinkNodejoin(LinkedXY, CountcurrentNode.getdYlink(),countStack);             }             return countStack.size();     }

④LinkNode类

public static class LinkNode{         int x;         int y;         LinkNode fxlink;//前         LinkNode bxlink;//后         LinkNode uylink;//上         LinkNode dylink;//下         //构造函数         public LinkNode (int x, int y) {             this.x = x;             this.y = y;             this.fxlink = null;             this.bxlink = null;             this.uylink = null;             this.dylink = null;          }         //方法体         //获得x坐标         public int getX() {             return x;         }         //设置x坐标//无用         public void setX(int x) {             this.x = x;         }         //获得y坐标         public int getY() {             return y;         }         //设置y坐标//无用         public void setY(int y) {             this.y = y;         }         //获取横f向链接         public LinkNode getfXlink() {             return fxlink;         }         //设置横f向链接         public void setfXlink(LinkNode fxlink) {             this.fxlink = fxlink;         }         //获取横b向链接         public LinkNode getbXlink() {             return bxlink;         }         //设置横b向链接         public void setbXlink(LinkNode bxlink) {             this.bxlink = bxlink;         }          //获取纵u向链接         public LinkNode getuYlink() {             return uylink;         }         //设置纵u向链接         public void setuYlink(LinkNode uylink) {             this.uylink = uylink;         }         //获取纵d向链接         public LinkNode getdYlink() {             return dylink;         }         //设置纵d向链接         public void setdYlink(LinkNode dylink) {             this.dylink = dylink;         }          //获得横f向链接坐标（返回string）         public String getfXlinkCoordinates(){             if (fxlink != null) {                 return "横前向链接的坐标：（"+fxlink.getX()+","+fxlink.getY();             } else {                 return "无横前向链接";             }         }         //获得横b向链接坐标         public String getbXlinkCoordinates(){             if (bxlink != null) {                 return "横后向链接的坐标：（"+bxlink.getX()+","+bxlink.getY();             } else {                 return "无横后向链接";             }         }         //获得纵u向链接坐标         public String getuYlinkCoordinates(){             if (uylink != null) {                 return "纵上向链接的坐标：（"+uylink.getX()+","+uylink.getY();             }else {                 return "无纵上向链接";             }         }         //获得纵d向链接坐标         public String getdYlinkCoordinates(){             if (uylink != null) {                 return "纵下向链接的坐标：（"+dylink.getX()+","+dylink.getY();             }else {                 return "无纵下向链接";             }         }         //自定义输出形式         public String toString(){             return "LinkNode{坐标=(" + x + ", " + y + ")" +                     ", 横前向链接=" + (fxlink != null ? "(" + fxlink.x + ", " + fxlink.y + ")" : "null") +                     ", 横后向链接=" + (bxlink != null ? "(" + bxlink.x + ", " + bxlink.y + ")" : "null") +                     ", 纵上向链接=" + (uylink != null ? "(" + uylink.x + ", " + uylink.y + ")" : "null") +                     ", 纵下向链接=" + (dylink != null ? "(" + dylink.x + ", " + dylink.y + ")" : "null") + "}\n";         }     }

三、运行结果

1.运行截图

2.带数据分析运行结果

[0,0]:0 [0,1]:1 [0,2]:1 [0,3]:0
[1,0]:1 [1,1]:1 [1,2]:1 [1,3]:0
[2,0]:1 [2,1]:1 [2,2]:0 [2,3]:0
[3,0]:1 [3,1]:0 [3,2]:1 [3,3]:1
[LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}
, LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}
, LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}
, LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}
, LinkNode{坐标=(1, 0), 横前向链接=null, 横后向链接=(1, 1), 纵上向链接=null, 纵下向链接=(2, 0)}
, LinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}
, LinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}
, LinkNode{坐标=(3, 0), 横前向链接=null, 横后向链接=null, 纵上向链接=null, 纵下向链接=null}
, LinkNode{坐标=(3, 2), 横前向链接=null, 横后向链接=(3, 3), 纵上向链接=null, 纵下向链接=null}
, LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}
]
LinkNodejoin：LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

当前countStack不含有该节点，加入进来啦！
fx:null
bx:LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

uy:null
dy:LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

当前CountcurrentNode为LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
bxlinkLinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

LinkNodejoin：LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

当前countStack不含有该节点，加入进来啦！
fx:LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

bx:null
uy:null
dy:LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前CountcurrentNode为LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
dylinkLinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkNodejoin：LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前countStack不含有该节点，加入进来啦！
fx:LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

bx:null
uy:null
dy:null
当前CountcurrentNode为LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
fxlinkLinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

LinkNodejoin：LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

当前countStack不含有该节点，加入进来啦！
fx:LinkNode{坐标=(1, 0), 横前向链接=null, 横后向链接=(1, 1), 纵上向链接=null, 纵下向链接=(2, 0)}

bx:LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

uy:null
dy:LinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前CountcurrentNode为LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
fxlinkLinkNode{坐标=(1, 0), 横前向链接=null, 横后向链接=(1, 1), 纵上向链接=null, 纵下向链接=(2, 0)}

LinkNodejoin：LinkNode{坐标=(1, 0), 横前向链接=null, 横后向链接=(1, 1), 纵上向链接=null, 纵下向链接=(2, 0)}

当前countStack不含有该节点，加入进来啦！
fx:null
bx:LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

uy:null
dy:LinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}

当前CountcurrentNode为LinkNode{坐标=(1, 0), 横前向链接=null, 横后向链接=(1, 1), 纵上向链接=null, 纵下向链接=(2, 0)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
dylinkLinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}

LinkNodejoin：LinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}

当前countStack不含有该节点，加入进来啦！
fx:null
bx:LinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

uy:null
dy:LinkNode{坐标=(3, 0), 横前向链接=null, 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前CountcurrentNode为LinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
bxlinkLinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkNodejoin：LinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前countStack不含有该节点，加入进来啦！
fx:LinkNode{坐标=(2, 0), 横前向链接=null, 横后向链接=(2, 1), 纵上向链接=null, 纵下向链接=(3, 0)}

bx:null
uy:null
dy:null
当前CountcurrentNode为LinkNode{坐标=(2, 1), 横前向链接=(2, 0), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
dylinkLinkNode{坐标=(3, 0), 横前向链接=null, 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkNodejoin：LinkNode{坐标=(3, 0), 横前向链接=null, 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前countStack不含有该节点，加入进来啦！
fx:null
bx:null
uy:null
dy:null
当前CountcurrentNode为LinkNode{坐标=(3, 0), 横前向链接=null, 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
LinkNodejoin：LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

fx:null
bx:LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

uy:null
dy:LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

当前CountcurrentNode为LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
LinkNodejoin：LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

当前countStack不含有该节点，加入进来啦！
fx:LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

bx:null
uy:null
dy:LinkNode{坐标=(1, 2), 横前向链接=(1, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

当前CountcurrentNode为LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
fxlinkLinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

LinkNodejoin：LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

当前countStack不含有该节点，加入进来啦！
fx:null
bx:LinkNode{坐标=(0, 2), 横前向链接=(0, 1), 横后向链接=null, 纵上向链接=null, 纵下向链接=(1, 2)}

uy:null
dy:LinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}

当前CountcurrentNode为LinkNode{坐标=(0, 1), 横前向链接=null, 横后向链接=(0, 2), 纵上向链接=null, 纵下向链接=(1, 1)}

LinkedXY的最后一个为LinkNode{坐标=(3, 3), 横前向链接=(3, 2), 横后向链接=null, 纵上向链接=null, 纵下向链接=null}

1---------------------------------------
dylinkLinkNode{坐标=(1, 1), 横前向链接=(1, 0), 横后向链接=(1, 2), 纵上向链接=null, 纵下向链接=(2, 1)}