2020百度Java工程师机考编程题

Sachi ·

更新时间:2024-09-21

· 763 次阅读

题目大意
牛牛和牛妹面前的桌子上有一个树状棋盘，棋盘由1～N个节点组成，其中，第1个节点是白色，第N个节点是黑色，剩余节点为无色，牛牛执白色，牛妹执黑色，牛牛先手；
每一步，牛牛可以选择一个白色节点，然后将该白色节点周围的一个无色节点涂成白色，牛妹可以选择一个黑色节点，然后将黑色节点周围的一个无色节点涂成黑色；当某人无法涂色（例如所有白色节点盘没有无色节点时），另一人获胜，现在要你判断谁能够获胜，如果牛牛获胜则输出“niuniu”，反之则输出“niumei”。

输入：
第一行为两个整数N和M分别代表节点数和节点中的连接数；
接下来N行，每行两个整数，表示这两个节点互相连接

测试用例：
7 6
1 2
1 4
4 5
2 6
6 7
2 3
niuniu

解题思路
本题难点主要在于如何处理这N个互相连接的节点，即如何表示节点之间的连接关系；
虽然题中说棋盘为“树状”，但我觉得更类似于无向图，不同于传统的无向图，本题还需要给每个节点标记一个“Color”field，原题中给出了树状棋盘的图，这里大家不妨在纸上画一画；
构建“Graph”后，要如何找出获胜者呢？不难想到，以白色为例，可以用一个队列存储白色节点的Edge，每次从队列中取出一个Edge，如果该Edge的to节点有颜色则选择其他点，直到队列为空（此处的获胜条件我觉得还有待商榷）。

以下为代码：

import java.util.*;
public class Main {
    private static int nodeNum;
    private static int edgeNum;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            nodeNum = scanner.nextInt();
            edgeNum = scanner.nextInt();
            Graph graph = new Graph();
            for (int i = 0; i < edgeNum; i++){
                int from = scanner.nextInt();
                int to = scanner.nextInt();
                //将节点存储到图中
                graph.addEdge(from,to);
            }
            graph.getWinner();
        }
    }
    public static class Graph {
        private class Node{
            private Integer value;
            //用一个ArrayList存储Node的Edge
            private List edges = new ArrayList();
            //Node的颜色属性，初始化为空白
            private String color = "blank";
            public Node(Integer value) {
                this.value = value;
            }
            private void addEdge(Node to){
                this.edges.add(new Edge(this,to));
            }
            public List getEdges(){
                return edges;
            }
            public String getColor() {
                return color;
            }
            public void setColor(String color) {
                this.color = color;
            }
        }
        private class Edge{
            private Node from;
            private Node to;
            public Edge(Node from, Node to) {
                this.from = from;
                this.to = to;
            }
        }
        //图用一个哈希表存储节点
        private HashMap nodes = new HashMap();
        public void addEdge(int from,int to){
            Node fromNode = nodes.get(from);
            //检查输入的节点是否存在，如果不存在则需要add该节点
            if (fromNode == null)
                nodes.put(from,new Node(from));
            Node toNode = nodes.get(to);
            if (toNode == null)
                nodes.put(to,new Node(to));
            //给from和to分别添加Edge
            nodes.get(from).addEdge(nodes.get(to));
            nodes.get(to).addEdge(nodes.get(from));
        }
        public void getWinner(){
            //用队列来存储Node的Edge,用于结下来的访问
            Queue whiteEdges = new ArrayDeque();
            Queue blackEdges = new ArrayDeque();
            //获取第1个节点
            Node whiteStart = nodes.get(1);
            //将节点颜色设置成白色
            whiteStart.setColor("white");
            //将该节点的Edge添加进白色点队列
            whiteEdges.addAll(whiteStart.getEdges());
            //获取第N个节点
            Node blackStart = nodes.get(nodeNum);
            blackStart.setColor("black");
            blackEdges.addAll(blackStart.getEdges());
            //结束条件为其中一个队列为空
            while (!whiteEdges.isEmpty() && !blackEdges.isEmpty()){
                //从白色队列中取出节点
                Edge whiteEdge = whiteEdges.poll();
                Node nextWhite = whiteEdge.to;
                //如果不是空白，则重新选择
                if (!nextWhite.getColor().equals("blank"))
                    continue;
                //将颜色设置成白色
                else nextWhite.setColor("white");
                whiteEdges.addAll(nextWhite.edges);
                Edge blackEdge = blackEdges.poll();
                Node nextBlack = blackEdge.to;
                if (!nextBlack.getColor().equals("blank"))
                    continue;
                else nextBlack.setColor("black");
                blackEdges.addAll(nextBlack.getEdges());
            }
            //此处判断条件还有待商榷
            if (whiteEdges.isEmpty())
                System.out.println("B");
            else System.out.println("A");
        }
    }
}

作者：zhangMANGO1998

java工程 JAVA

1024 个赞