Domino Tiling - M x N Board with Holes

solve.js

class Queue {
  constructor() {
    this.list = []
    this.head = 0
  }
  push(e) { this.list.push(e) }
  pop() { return this.list[this.head++] }
  empty() { return this.list.length == this.head }
}

const NIL = 'X'

class HopcroftKarp {
  constructor(grid) {
    this.queue = new Queue()
    this.pairU = {}
    this.pairV = {}
    this.dist = {}
    this.adj = {}
    this.U = []
    this.V = []
    
    let coords = grid.map((row, r) => row.map((_, c) => r + ',' + c))
    let rows = grid.length, cols = grid[0].length
    for (let r = 0; r < rows; ++r) for (let c = 0; c < cols; ++c) {
      if (!grid[r][c]) continue
      if ((r + c) % 2 == 0) this.U.push(coords[r][c])
      else this.V.push(coords[r][c])
      
      let adj = [[r+1, c], [r, c+1], [r-1, c], [r, c-1]].filter(
        ([r2, c2]) => r2 >= 0 && r2 < rows && c2 >= 0 && c2 < cols && grid[r2][c2]
      ).map(([r2, c2]) => coords[r2][c2])
      this.adj[coords[r][c]] = adj
    }
  }
  
  bfs() {
    for (let u of this.U) {
      if (this.pairU[u] === NIL) {
        this.dist[u] = 0
        this.queue.push(u)
      }
      else this.dist[u] = Infinity
    }
    this.dist[NIL] = Infinity
    while (!this.queue.empty()) {
      let u = this.queue.pop()
      if (this.dist[u] < this.dist[NIL]) {
        for (let v of this.adj[u]) {
          if (this.dist[this.pairV[v]] == Infinity) {
            this.dist[this.pairV[v]] = this.dist[u] + 1
            this.queue.push(this.pairV[v])
          }
        }
      }
    }
    return this.dist[NIL] != Infinity
  }
  
  dfs(u) {
    if (u != NIL) {
      for (let v of this.adj[u]) {
        if (this.dist[this.pairV[v]] == this.dist[u] + 1) {
          if (this.dfs(this.pairV[v])) {
            this.pairV[v] = u
            this.pairU[u] = v
            return true
          }
        }
      }
      this.dist[u] = Infinity
      return false
    }
    return true
  }
  
  run() {
    for (let u of this.U) this.pairU[u] = NIL
    for (let v of this.V) this.pairV[v] = NIL
    let matching = 0
    while (this.bfs()) {
      for (let u of this.U) {
        if (this.pairU[u] == NIL && this.dfs(u)) matching++
      }
    }
    return matching
  }
}

function maxDominoTiling(grid) {
  return new HopcroftKarp(grid).run()
}