返回信息流昨天晚上百度校招的编程题，题目如下：
为了制定城市规划方案，正在对一个居民区内的住宅进行研究。
该居民区俯视图已经制作好，并划分成 n*m个网格。如果某个网格单元具有屋顶的一部分，则向其赋值1，如果是空地，则赋值0。由值为1的相邻网格单元组成的簇认定为一个单独住宅。对角放置的值为1的网格则不被视为属于属于同一住宅/屋顶。
求最大面积的住宅。
我的代码如下：
```
public class Solution {
private static int[] par = new int[11111];
private static int[] ran = new int[11111];
private static int ans=1,k,cnt=0;
private static void union(int i, int j) {
i=find(i);
j=find(j);
if(i==j)
return;
if(i>j) {
par[i]=j;
//ran[j]+=ran[i];
ran[j]++;
if(ans<ran[j]) {
ans=ran[j];
k=j;
}
}
else {
par[j]=i;
//ran[i]+=ran[j];
ran[i]++;
if(ans<ran[i]) {
ans=ran[i];
k=i;
}
}
}
private static int find(int i) {
int r=i;
while(r!=par[r])
r=par[r];
return r;
}
public static int bigHouse(int[][] grid) {
int n=grid.length;
int m=grid[0].length;
for(int i=0;i<n*m;i++) {
par[i]=i;ran[i]=1;
}
int flag=0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(grid[i][j]==1) {
//union right
flag=1;
if(j<m-1 && grid[i][j+1]==1)
union(i*m+j,i*m+j+1);
//union left
if(j>0 && grid[i][j-1]==1)
union(i*m+j,i*m+j-1);
//union up
if(i>0 && grid[i-1][j]==1)
union(i*m+j, (i-1)*m+j);
//union down
if(i<n-1 && grid[i+1][j]==1)
union(i*m+j, (i+1)*m+j);
}
}
}
if(flag==0)
return 0;
return ans;
}
}
```
结果是无限WA，提示错误测试点：
0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0
正确答案为1，我的返回值为3.
十分不解，明明在本地调用确实返回为1啊。。。
求大神帮看看错在哪了？
附测试代码：
```
public class Main{
public static void main(String[] args) {
int[][] grid = new int[][] {
{0,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,0},
};
System.out.println(Solution.bigHouse(grid));
}
}
```
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91165同步于 2016/9/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[问题]昨晚百度校招编程题之数最大的房子
lhy963
2016/9/21镜像同步36 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
扫描线算法？扯远了吧，又不是计算几何
就是统计一个01矩阵中连起来的最多的1的个数
【 在 nuanyangyang 的大作中提到: 】
: 用扫描线算法试试？直觉告诉我没有这么麻烦。
【 在 lhy963 的大作中提到: 】
: 扫描线算法？扯远了吧，又不是计算几何
: 就是统计一个01矩阵中连起来的最多的1的个数
我没开玩笑。一条线穿过“当前列的所有点”，然后，这一列上每个点的“领导”（所属的集合）、每个点的“累计面积”，都只和上一列本行，以及当前列上下两行的点有关。这条线从左向右扫描，扫一遍，最大的连续区块就得到了。
说它是个离散型的扫描线也行，说它是动态规划也行。
有比O(N)更快的？
O(1)的who TMD cares算法么？
【 在 Thesharing 的大作中提到: 】
: 连通块用DFS理解起来简单一点…… 不过复杂度有点高？小白一个……