问题遇到的现象和发生背景
遇到的现象和发生背景,请写出第一个错误信息
用代码块功能插入代码,请勿粘贴截图。 不用代码块回答率下降 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;
}
}