Minimum operations to remove adjacent ones in matrix

impl Solution {
  pub fn minimum_operations(grid: Vec<Vec<i32>>) -> i32 {
    // This is a minimum vertex cover on a bipartite graph problem.
    // Model 1-cells on even columns as left, odd columns as right.
    // Edges between adjacent 1s. By König's theorem, min vertex cover = max matching.
    // Use Hungarian/Hopcroft-Karp algorithm for maximum bipartite matching.
    let m = grid.len();
    let n = grid[0].len();
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    
    // Build adjacency: for each 1-cell, find adjacent 1-cells
    // We'll do matching where left = cells at even (r+c), right = cells at odd (r+c)
    let id = |r: usize, c: usize| -> usize { r * n + c };
    
    // Build adj list for left nodes (even parity)
    let mut adj: Vec<Vec<usize>> = vec![vec![]; m * n];
    for r in 0..m {
      for c in 0..n {
        if grid[r][c] == 1 && (r + c) % 2 == 0 {
          for &(dr, dc) in &dirs {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
              let nr = nr as usize;
              let nc = nc as usize;
              if grid[nr][nc] == 1 {
                adj[id(r, c)].push(id(nr, nc));
              }
            }
          }
        }
      }
    }
    
    let mut match_right = vec![usize::MAX; m * n];
    let mut result = 0;
    
    for r in 0..m {
      for c in 0..n {
        if grid[r][c] == 1 && (r + c) % 2 == 0 {
          let mut visited = vec![false; m * n];
          if Self::dfs(id(r, c), &adj, &mut match_right, &mut visited) {
            result += 1;
          }
        }
      }
    }
    
    result
  }
  
  fn dfs(u: usize, adj: &[Vec<usize>], match_right: &mut [usize], visited: &mut [bool]) -> bool {
    for &v in &adj[u] {
      if !visited[v] {
        visited[v] = true;
        if match_right[v] == usize::MAX || Self::dfs(match_right[v], adj, match_right, visited) {
          match_right[v] = u;
          return true;
        }
      }
    }
    false
  }
}