欢迎光临
我们一直在努力

DeepSeek LintCode 3888 · 使矩阵中的 1 互不相邻的最小操作数 public int minimumOperations(int[][] grid)

问题分析

这个问题是:给定一个 0-1 矩阵,我们可以进行操作:将 1 翻转为 0(不能将 0 翻转为 1)。目标是使矩阵中没有两个 1 是相邻的(相邻指上下左右四个方向,不包括对角线)。求最小的操作次数。

换句话说,我们需要删除最少的 1,使得剩下的 1 构成一个独立集(没有边相连)。


思路分析

观察

矩阵中的 1 形成一些连通分量(通过上下左右连接)。每个连通分量内的 1 都互相冲突(相邻)。为了让 1 互不相邻,我们必须保留一个独立集——即图中没有边相连的顶点集合。

这实际上是:在网格图中,每个 1 是一个顶点,如果两个 1 相邻则有边。我们需要删除最少的顶点,使得剩下的顶点构成一个独立集。

等价于:求最大独立集(Maximum Independent Set, MIS),然后删除的顶点数 = 总1数 – |MIS|。


网格图的性质

网格图是二分图。因为我们可以用 (行+列) 的奇偶性来划分:

  • 将格子 (i,j) 分为两类:当 (i+j) 为偶数的为黑色,奇数为白色。
  • 在网格中,相邻的两个格子颜色一定不同。

因此这个图是二分图,问题转化为:在二分图中求最大独立集。


二分图中的最大独立集

对于任意图:最大独立集 = 总顶点数 – 最小顶点覆盖数。

对于二分图,根据König定理:最小顶点覆盖数 = 最大匹配数。

因此:

  • 最大独立集大小 = 总顶点数 – 最大匹配数
  • 需要删除的顶点数 = 总1数 – (总顶点数 – 最大匹配数) = 最大匹配数

结论:需要的最小操作数 = 该二分图的最大匹配数。


算法步骤

  • 构建二分图:

    • 将矩阵中所有值为 1 的格子视为顶点。
    • 将顶点按 (i+j) % 2 分为左部(偶)和右部(奇)。
    • 对于每个 1,检查其四个方向的邻居,如果邻居也是 1,则添加一条无向边(在二分图中是左部到右部的边)。
  • 求最大匹配:

    • 使用匈牙利算法(DFS增广)或Hopcroft-Karp算法(更快)。
    • 因为我们只需要左部到右部的匹配,可以用标准的二分图最大匹配算法。
  • 答案:

    • 总1的个数 = 矩阵中1的总数
    • 最大独立集大小 = 总1数 – 最大匹配数
    • 最小操作数 = 总1数 – 最大独立集大小 = 最大匹配数

  • 具体实现细节

    顶点编号

    为了方便,给每个 1 的格子一个唯一编号(从 0 开始)。同时维护左右两部各自的顶点列表。

    邻接表

    对于左部的每个顶点,存储它到右部邻居的边(只存右部顶点的编号)。

    匈牙利算法

    • matchR[]:右部顶点匹配的左部顶点编号,初始为 -1。
    • 对左部的每个顶点 u,进行 DFS 找增广路。
    • visited[]:标记右部顶点在本轮 DFS 中是否访问过。

    代码实现

    import java.util.*;

    public class Solution {


    public int minimumOperations(int[][] grid) {


    int m = grid.length;
    int n = grid[0].length;

    // 给每个为1的格子一个唯一编号
    int[][] id = new int[m][n];
    for (int i = 0; i < m; i++) {


    Arrays.fill(id[i], –1);
    }

    List<Integer> left = new ArrayList<>(); // (i+j) 偶数的1

    赞(0)
    未经允许不得转载:171主机测评 » DeepSeek LintCode 3888 · 使矩阵中的 1 互不相邻的最小操作数 public int minimumOperations(int[][] grid)
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址