java 解法, 执行用时: 12 ms, 内存消耗: 39.2 MB, 提交时间: 2023-10-27 22:26:01

// 回溯算法，适用于我这种菜鸟，不过看懂匈牙利也挺简单的。
class Solution {
    private int[][] board;// 棋盘
    private int n, m;// 行数，列数

    public int domino(	int n,
                        int m,
                        int[][] broken) {
		if (broken.length == 0) {
			return n * m >> 1;
		}

        board = new int[n][m];

        for (int[] b : broken) {
            board[b[0]][b[1]] = 2;// 坏掉
        }

        this.n = n;
        this.m = m;
        return backtrack(0, 0, 0);
    }

	// (r, c)当前位置，count已经放的骨牌数
    private int backtrack(	int r,
                            int c,
                            int count) {
        if (r >= n) {// 行越界，结束，返回最大值
            return count;
        }
        if (c >= m) {// 列越界
            return backtrack(r + 1, 0, count);// 转到下一行，骨牌数不变
        }
        if (board[r][c] != 0) {// 当前位置已经有骨牌或者坏掉
            return backtrack(r, c + 1, count);// 转到下一列，骨牌数不变
        }

        int count1 = 0;// 横放
        if (c + 1 < m && board[r][c + 1] == 0) {// 右边未出界并且可以放骨牌
            board[r][c] = board[r][c + 1] = 1;
            count1 = backtrack(r, c + 2, count + 1);// 转到下下一列，骨牌数加1
            board[r][c] = board[r][c + 1] = 0;// 复盘
        }

        int count2 = 0;// 竖放
        if (r + 1 < n && board[r + 1][c] == 0) {// 未出界并且可以放骨牌
            board[r][c] = board[r + 1][c] = 1;
            count2 = backtrack(r, c + 1, count + 1);// 转到下一列，骨牌数加1
            board[r][c] = board[r + 1][c] = 0;
        }

        int count3 = 0;// 不放
        if (count1 == 0 && count2 == 0) {// 无法放骨牌，不放
            count3 = backtrack(r, c + 2, count);// 转到下下一列，骨牌数不变
        }

        return Math.max(Math.max(count1, count2), count3);// 返回最大值
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-27 22:25:48

// 匈牙利算法
class Solution {
    private boolean[] visit;// visit[v2]=true表示点v2访问过
    private int[] link;// link[v2]=v1表示当前与v2相连的点是v1
    // 其中v1属于点集V1，v2属于点集V2，数组下标从0开始

    private boolean[][] board;// 棋盘，false表示坏的
    private int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };

    public int domino(int n, int m, int[][] broken) {
        if (broken.length == 0) {// 无坏掉的
            return n * m >> 1;
        }

        // 初始化棋盘，false表示坏掉
        board = new boolean[n][m];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(board[i], true);// 初始全部完好
        }
        for (int[] b : broken) {
            board[b[0]][b[1]] = false;// 设置坏掉的
        }

        return hungary();// 匈牙利算法计算最大骨牌数
    }

    private int hungary() {// 匈牙利算法，返回最大匹配数
        int n = board.length, m = board[0].length;
        visit = new boolean[n * m];
        link = new int[n * m];
        Arrays.fill(link, -1);
        int ret = 0;
        // 遍历点集V1中的点
        for (int r = 0; r < n; ++r) {
            for (int c = ((r & 1) == 0 ? 0 : 1); c < m; c += 2) {
                if (board[r][c]) {
                    Arrays.fill(visit, false);
                    if (find(r, c)) {
                        ++ret;
                    }
                }
            }
        }
        return ret;// 返回最大匹配数
    }

    private boolean find(int row, int col) {
        int n = board.length, m = board[0].length;
        for (int[] d : dir) {// 四个相邻点
            int r = row + d[0];
            int c = col + d[1];
            if (r < 0 || r >= n || c < 0 || c >= m) {
                continue;// 越界
            }
            int v2 = r * m + c;
            if (board[r][c] && !visit[v2]) {// 完好并且未访问过
                visit[v2] = true;
                if (link[v2] == -1 || find(link[v2] / m, link[v2] % m)) {
                    link[v2] = row * m + col;
                    return true;// 找到增广路径
                }
            }
        }
        return false;// 找不到增广路径
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-27 22:24:32

class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        #相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）
        Row, Col = n, m

        match = [[None for _ in range(Col)] for _ in range(Row)]
        for r, c in broken:
            match[r][c] = '#'           #这个点不能被匹配

        def dfs(r: int, c: int, visited: set()) -> bool:        #find增广路径  模板 visit直接在参数里传递了
            visited.add((r, c))
            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)): #有连接的边
                if 0<= nr < Row and 0<= nc < Col:               #有连接的边
                    nxt = match[nr][nc]     #寻找增广路径

                    if nxt in visited:      #没访问过，且不是坑（坑已经在visited里面了）
                        continue
                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True: #如果还没配对，或者配的对可以找到增广路径
                        match[r][c] = (nr, nc)
                        match[nr][nc] = (r, c)
                        return True
            return False

        res = 0
        for r in range(Row):
            for c in range(Col):
                if (r + c) % 2 == 0:            #从偶集开始，从奇数集开始也行
                    if (match[r][c] != '#'):
                        if dfs(r, c, {'#'}) == True:
                            res += 1
        return res

cpp 解法, 执行用时: 104 ms, 内存消耗: 34.1 MB, 提交时间: 2023-10-27 22:24:05

class Solution 
{
public:
    int Row, Col;
    vector<vector<pair<int,int>>> match;

    int domino(int n, int m, vector<vector<int>>& broken) 
    {
        Row = n;    Col = m;
        match = vector<vector<pair<int,int>>> (Row, vector<pair<int,int>>(Col, pair<int,int>{-5,-5}) ); //还没配对，就赋个{-5，-5}
        for (auto v: broken)
        {
            int r = v[0],   c = v[1];
            match[r][c] = pair<int,int>(-1, -1);  //坑，不能匹配
        }

        int res = 0;
        set<pair<int,int>> init_visited;
        init_visited.insert(pair<int,int>{-1, -1}); //把坑当成visited了，就不用额外判断了。

        for (int r = 0; r < Row; r ++)
            for (int c = 0; c < Col; c ++)
                if ((r + c) % 2 == 0)       //0和1都可以。奇集和偶集!!!!!!!!!!!!!!!!!
                    if (match[r][c] != pair<int,int>{-1, -1})
                        if (dfs(r, c, init_visited) == true)
                            res ++;
        return res;
    }

    //std::function<bool (int, int, unordered_set<pair<int,int>>) > dfs = [&] (int r, int c, set<pair<int,int>> visited)    //func不行，因为visited传递不了
    bool dfs(int r, int c, set<pair<int,int>> visited)
    {
        visited.insert(pair<int,int>{r, c});   //记忆化               我是男生
        for (auto[nr, nc] : vector<pair<int,int>>{{r-1,c}, {r+1,c}, {r,c-1}, {r,c+1}})  //所有可能相邻的边(女生)
        {
            if (0 <= nr && nr < Row && 0 <= nc && nc < Col)   //相邻的边     可以接触到的女生
            {
                pair<int,int> her_bf = match[nr][nc];     //临边的配对  这个女神的男朋友
                if (visited.count(her_bf) != 0)     //她的男朋友，已经被商量试验过了
                    continue;
                
                if (her_bf == pair<int,int>{-5,-5} || dfs(her_bf.first, her_bf.second, visited) == true )  //这个女生没有男朋友，或者她男朋友可以再找
                {
                    match[r][c] = {nr, nc};   //我和这个妹纸，就成了一对cp
                    match[nr][nc] = {r, c};   //妹纸和我就成了一对cp
                    return true;
                }
            }
        }
        return false;
    };

};

cpp 解法, 执行用时: 0 ms, 内存消耗: 8.9 MB, 提交时间: 2023-10-27 22:23:06

class BinaryGraph {
public: 
    vector<vector<int> > g;
    vector<int> pa;  // 匹配
    vector<int> pb;
    vector<int> vis;  // 访问
    int n, m;         // 两个点集中的顶点数量
    int dfn;          // 时间戳记
    int res;          // 匹配数

    // 二分图初始化
    void init(int _n, int _m) {
        n = _n;
        m = _m;
        pa = vector<int>(n, -1);
        pb = vector<int>(m, -1);
        vis = vector<int>(n);
        g.resize(n);
        res = 0;
        dfn = 0;
    }

    // 加边函数
    void add(int from, int to) {
        g[from].push_back(to);
    }

    // 最大匹配
    bool dfs(int v) {
        vis[v] = dfn;
        for (int u : g[v]) {
            if (pb[u] == -1) {
                pb[u] = v;
                pa[v] = u;
                return true;
            }
        }
        for (int u : g[v]) {
            if (vis[pb[u]] != dfn && dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int solve() {
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

class Solution {
public:
    int x[4] = {-1, 0, 1, 0};
    int y[4] = {0, 1, 0, -1};

    int domino(int n, int m, vector<vector<int>>& broken) {
        // 建图，若为 0 则不能放多米诺骨牌，否则可以放置
        vector<vector<int>> graph(n, vector<int>(m, 1));
        for(auto b : broken) graph[b[0]][b[1]] = 0;

        // 初始化二分图
        BinaryGraph *bg = new BinaryGraph();
        bg->init(n * m, n * m);

        // 深度优先搜索，加边
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!graph[i][j]) continue;
                // (i, j) -> 四边扩展
                for(int k = 0; k < 4; k++) {
                    int dx = i + x[k], dy = j + y[k];
                    if(dx < 0 || dx >= n || dy < 0 || dy >= m || !graph[dx][dy]) continue;
                    if((i + j) % 2 == 0) bg->add(i * m + j, dx * m + dy);
                }
            }
        }
        
        // 求解
        return bg->solve();
    }
};