躲过了两次裁员，终于成为腾讯员工了!!!

真有点打工人玄学那味儿了。

喜马拉雅这波员工心情估计挺复杂。前面裁员风声一阵一阵的，能留下来的人，本来就算是闯关成功了。结果现在腾讯收购审批过了，好像直接换厂牌了。

最搞的是网友那句，躲过两轮裁员，最后熬成腾讯员工。听着像段子，其实打工人都懂，这里面哪有什么爽文，全是“别轮到我”的小心翼翼。

但话说回来，这种事确实太戏剧了。昨天还在担心公司下一步咋走，今天突然发现工牌背后站了个大厂。HR估计也得沉默两秒，这员工情绪转得比版本发布还快。

只能说职场有时候真不是努力就能解释的，运气来了，连组织架构都帮你跳槽。

矩阵里扫到一个 1，别急着上 DFS。

这题叫“找到所有的农场组”，给你一个只包含 0 和 1 的二维数组，1 表示农田，0 表示空地。题目还给了一个很关键的条件：每块农场都是一个矩形，而且不同农场之间不会相邻。

这个条件别白给。

我第一眼看到这题，不太想写 DFS。不是不能写，DFS 肯定能过，但它把一个本来很规整的问题写散了。既然农场一定是矩形，那我们扫到某个还没处理过的 1 时，这个点大概率就是一块农场的左上角。

然后往右找边界，往下找边界，就能确定这个矩形：

1 1 0
1 1 0
0 0 1

扫到 (0,0)，往右能到第 1 列，往下能到第 1 行，所以第一块农场就是：

[0, 0, 1, 1]

后面的 (2,2) 是单独一块：

[2, 2, 2, 2]

我写这题时一般直接把处理过的农场改成 0。省一个 visited 数组，也不绕。算法题里只要题目没要求保留原数组，这种写法很干净。

Java 代码如下：

import java.util.ArrayList;
import java.util.List;

classSolution{

publicint[][] findFarmland(int[][] land) {
int rowCount = land.length;
int colCount = land[0].length;

        List<int[]> ans = new ArrayList<>();

for (int row = 0; row < rowCount; row++) {
for (int col = 0; col < colCount; col++) {

if (land[row][col] == 0) {
continue;
                }

int bottom = row;
int right = col;

while (bottom + 1 < rowCount && land[bottom + 1][col] == 1) {
                    bottom++;
                }

while (right + 1 < colCount && land[row][right + 1] == 1) {
                    right++;
                }

                clearFarm(land, row, col, bottom, right);

                ans.add(newint[]{row, col, bottom, right});
            }
        }

return ans.toArray(newint[ans.size()][]);
    }

privatevoidclearFarm(int[][] land, int top, int left, int bottom, int right){
for (int i = top; i <= bottom; i++) {
for (int j = left; j <= right; j++) {
                land[i][j] = 0;
            }
        }
    }
}

这里有个地方容易写别扭。

有人会在每个 1 上判断它是不是左上角，比如判断上边和左边是不是 0。也能做，但判断多了，代码反而碎。我的习惯是：扫到没处理过的 1，直接认定它是一块新农场的起点，然后把整块农场清掉。后面再扫到这块区域时，已经是 0 了，不会重复处理。

这类题最怕把条件浪费掉。

题目已经保证农场是矩形，那就不要把它当成普通连通块来做。普通连通块需要 BFS、DFS、队列、递归栈；矩形农场只需要找右边界和下边界。

复杂度也比较直观。

每个格子最多被扫描、清理一次，时间复杂度是 O(m * n)。除了结果数组以外，没有额外开大空间，额外空间可以看成 O(1)。

如果面试官要求不能修改原数组，把 land[i][j] = 0 换成一个 boolean[][] visited 就行，思路不用变。 但真写题的时候，我会优先用原地标记，少一层状态，少一层出错点。