aming12321_ 2023-03-15 14:52 采纳率: 81.8%
浏览 10

关于最大连通子量的问题,如何解决?

问题遇到的现象和发生背景
遇到的现象和发生背景,请写出第一个错误信息
用代码块功能插入代码,请勿粘贴截图。 不用代码块回答率下降 50%
运行结果及详细报错内容
我的解答思路和尝试过的方法,不写自己思路的,回答率下降 60%
我想要达到的结果,如果你需要快速回答,请尝试 “付费悬赏”

最大连通子量,用的是bfs ,应该输出7,但一直输出5,有人指点一下吗

ublic class Maxliantong{
        /*问题描述
    小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。
    
    
    
    
    如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置,则称两个位置连通。
    与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。
    
    请问矩阵中最大的连通分块有多大
    
    思路
    1.bfs
    2.dfs
    */
    public static int[]fx = {1,0,-1,0};
    public static int[]fy = {0,1,0,-1};//移动方向 下右上左
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [][] arr = new int[][] {{0,0,1,0},{0,1,1,1},{1,0,1,0},{0,0,1,1}};
        int max = 0;
        max = bfs(arr,max);
        System.out.println(max);
    }

    private static int bfs(int[][] arr, int max) {
        // TODO Auto-generated method stub
        
        Queue<Node1> queue = new LinkedList<Node1>();
        Node1 node = new Node1();
        int count = 0;//记录连通的数量
        
        for(int i = 0 ; i<4 ; i++) {
            for(int j = 0 ; j <4 ; j++) {
                if(arr[i][j]==1) {
                    node.x = i;
                    node.y = j;
                    queue.offer(node);
                    count++;
                    while(!queue.isEmpty()) {
                        //遍历该节点的上下左右位
                        node=queue.poll();//弹出为1的量
                        int x1 = node.x;
                        int y1 = node.y;
                        arr[x1][y1]=0;//置为0,避免重复
                        for(int k = 0 ; k < 4 ;k++) {
                            int x2 = x1+fx[k];
                            int y2 = y1+fy[k];
                            if(x2>=0&&x2<4&&y2>=0&&y2<4&&arr[x2][y2]==1) {
                                node.x = x2;
                                node.y = y2;
                                queue.offer(node);
                                //arr[x2][y2]=0;
                                count++;
                                System.out.println(x2+" "+y2+"    "+count);
                            }
                            
                        }
                        
                    }//while结束 说明已经找到所有直接与间接相连的
                    max = Math.max(max, count);
                    count = 0;//count置为0 重新计数
                }
                
            }
        }
        
        return max;
    }

}
class Node1{
    int x ;
    int y ;
    /**
     * @param x
     * @param y
     */
    public Node1() {}
    public Node1(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    
}

  • 写回答

1条回答 默认 最新

  • threenewbee 2023-03-15 14:58
    关注

    代码自己调试下,应该是代码方面的错误。

    评论

报告相同问题?

问题事件

  • 创建了问题 3月15日

悬赏问题

  • ¥115 关于#python#的问题:未加密前两个软件都可以打开,加密后只有A软件可打开,B软件可以打开但读取不了数据
  • ¥15 在matlab中Application Compiler后的软件无法打开
  • ¥15 想问一下STM32创建工程模板时遇到得问题
  • ¥15 Fiddler抓包443
  • ¥20 Qt Quick Android 项目报错及显示问题
  • ¥15 而且都没有 OpenCVConfig.cmake文件我是不是需要安装opencv,如何解决?
  • ¥15 oracleBIEE analytics
  • ¥15 H.264选择性加密例程
  • ¥50 windows的SFTP服务器如何能批量同步用户信息?
  • ¥15 centos7.9升级python3.0的问题