Hard

题目描述

给你一个 n x n 的二进制网格 board。在每一次移动中，你可以交换任意两行之间的位置，或者交换任意两列之间的位置。

返回将此数组变为"棋盘"所需的最小移动次数。如果不存在可行的变换，输出 -1。

“棋盘"是指黑白格相间的数组，即任意一个数字的上下左右四个方向的数字都与该数字不同。

示例 1：

输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释: 一个可行的变换序列是第一行图向第二行图的变化。
第一次移动交换了第一和第二列。
第二次移动交换了第二和第三行。

示例 2：

输入: board = [[0,1],[1,0]]
输出: 0
解释: 注意左上角的格值为0也是一种可行的棋盘，也是合法的。

示例 3：

输入: board = [[1,0],[1,0]]
输出: -1
解释: 任意的变换都无法变为合法的棋盘。

提示：

  • n == board.length
  • n == board[i].length
  • 2 <= n <= 30
  • board[i][j] 是 0 或 1

解题思路

解题思路

棋盘变换问题的关键在于理解棋盘的性质和变换规律。

核心观察：

  1. 在一个合法的棋盘中，只能存在两种不同的行模式和两种不同的列模式
  2. 这两种模式必须是互补的（如 01010... 和 10101...）
  3. 每种模式的数量差不能超过1

算法步骤：

  1. 验证可行性：检查是否只有两种行模式和两种列模式，且它们互为补集
  2. 计算最小移动次数：
    • 对于行：计算当前排列到目标排列的最小交换次数
    • 对于列：同样计算最小交换次数
    • 如果 n 是偶数，有两种可能的目标模式，选择移动次数较小的
    • 如果 n 是奇数，目标模式唯一确定（较多的模式必须在偶数位置）

关键点：

  • 交换相邻两个错位元素的最小次数 = 错位元素个数 / 2
  • 需要分别处理奇偶大小的棋盘，因为它们的约束条件不同

这个问题结合了位操作、数学推理和贪心算法的思想，是一道综合性较强的题目。

代码实现

class Solution {
public:
    int movesToChessboard(vector<vector<int>>& board) {
        int n = board.size();
        
        // Check if transformation is possible
        // There should be exactly 2 kinds of rows and 2 kinds of columns
        map<vector<int>, int> rowCount, colCount;
        
        for (int i = 0; i < n; i++) {
            rowCount[board[i]]++;
            vector<int> col;
            for (int j = 0; j < n; j++) {
                col.push_back(board[j][i]);
            }
            colCount[col]++;
        }
        
        if (rowCount.size() != 2 || colCount.size() != 2) return -1;
        
        // Check if the two row patterns are complementary
        vector<vector<int>> rows;
        vector<int> rowCounts;
        for (auto& p : rowCount) {
            rows.push_back(p.first);
            rowCounts.push_back(p.second);
        }
        
        vector<vector<int>> cols;
        vector<int> colCounts;
        for (auto& p : colCount) {
            cols.push_back(p.first);
            colCounts.push_back(p.second);
        }
        
        // Check if rows are complementary
        for (int i = 0; i < n; i++) {
            if (rows[0][i] == rows[1][i]) return -1;
        }
        
        // Check if cols are complementary
        for (int i = 0; i < n; i++) {
            if (cols[0][i] == cols[1][i]) return -1;
        }
        
        // Check count constraints
        if (abs(rowCounts[0] - rowCounts[1]) > 1) return -1;
        if (abs(colCounts[0] - colCounts[1]) > 1) return -1;
        
        // Calculate minimum moves for rows
        int rowMoves = calculateMoves(rows, rowCounts, n);
        
        // Calculate minimum moves for cols
        int colMoves = calculateMoves(cols, colCounts, n);
        
        return rowMoves + colMoves;
    }
    
private:
    int calculateMoves(vector<vector<int>>& patterns, vector<int>& counts, int n) {
        vector<int> target(n);
        
        if (n % 2 == 1) {
            // For odd n, the pattern with more occurrences should start with the more frequent element
            vector<int> pattern = (counts[0] > counts[1]) ? patterns[0] : patterns[1];
            for (int i = 0; i < n; i++) {
                target[i] = pattern[0] ^ (i % 2);
            }
        } else {
            // For even n, try both possibilities and take minimum
            vector<int> target1(n), target2(n);
            for (int i = 0; i < n; i++) {
                target1[i] = patterns[0][0] ^ (i % 2);
                target2[i] = patterns[1][0] ^ (i % 2);
            }
            
            int moves1 = getMismatchCount(patterns, counts, target1) / 2;
            int moves2 = getMismatchCount(patterns, counts, target2) / 2;
            
            return min(moves1, moves2);
        }
        
        return getMismatchCount(patterns, counts, target) / 2;
    }
    
    int getMismatchCount(vector<vector<int>>& patterns, vector<int>& counts, vector<int>& target) {
        int mismatches = 0;
        for (int i = 0; i < patterns.size(); i++) {
            for (int j = 0; j < target.size(); j++) {
                if (patterns[i][j] != target[j]) {
                    mismatches += counts[i];
                    break;
                }
            }
        }
        return mismatches;
    }
};

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        
        # Count different row and column patterns
        row_patterns = {}
        col_patterns = {}
        
        for i in range(n):
            row_tuple = tuple(board[i])
            row_patterns[row_tuple] = row_patterns.get(row_tuple, 0) + 1
            
            col_tuple = tuple(board[j][i] for j in range(n))
            col_patterns[col_tuple] = col_patterns.get(col_tuple, 0) + 1
        
        # Must have exactly 2 patterns for both rows and columns
        if len(row_patterns) != 2 or len(col_patterns) != 2:
            return -1
        
        # Get patterns and their counts
        rows = list(row_patterns.keys())
        row_counts = list(row_patterns.values())
        cols = list(col_patterns.keys())
        col_counts = list(col_patterns.values())
        
        # Check if patterns are complementary
        for i in range(n):
            if rows[0][i] == rows[1][i] or cols[0][i] == cols[1][i]:
                return -1
        
        # Check count constraints
        if abs(row_counts[0] - row_counts[1]) > 1 or abs(col_counts[0] - col_counts[1]) > 1:
            return -1
        
        def calculate_moves(patterns, counts):
            if n % 2 == 1:
                # For odd n, determine the target pattern
                start_bit = patterns[0][0] if counts[0] > counts[1] else patterns[1][0]
                target = tuple(start_bit ^ (i % 2) for i in range(n))
            else:
                # For even n, try both possibilities
                target1 = tuple(patterns[0][0] ^ (i % 2) for i in range(n))
                target2 = tuple(patterns[1][0] ^ (i % 2) for i in range(n))
                
                moves1 = sum(counts[i] for i, pattern in enumerate(patterns) if pattern != target1) // 2
                moves2 = sum(counts[i] for i, pattern in enumerate(patterns) if pattern != target2) // 2
                
                return min(moves1, moves2)
            
            return sum(counts[i] for i, pattern in enumerate(patterns) if pattern != target) // 2
        
        row_moves = calculate_moves(rows, row_counts)
        col_moves = calculate_moves(cols, col_counts)
        
        return row_moves + col_moves

public class Solution {
    public int MovesToChessboard(int[][] board) {
        int n = board.Length;
        
        // Count row and column patterns
        var rowPatterns = new Dictionary<string, int>();
        var colPatterns = new Dictionary<string, int>();
        
        for (int i = 0; i < n; i++) {
            string rowKey = string.Join("", board[i]);
            rowPatterns[rowKey] = rowPatterns.GetValueOrDefault(rowKey, 0) + 1;
            
            string colKey = "";
            for (int j = 0; j < n; j++) {
                colKey += board[j][i].ToString();
            }
            colPatterns[colKey] = colPatterns.GetValueOrDefault(colKey, 0) + 1;
        }
        
        if (rowPatterns.Count != 2 || colPatterns.Count != 2) {
            return -1;
        }
        
        var rows = new List<string>(rowPatterns.Keys);
        var rowCounts = new List<int> { rowPatterns[rows[0]], rowPatterns[rows[1]] };
        var cols = new List<string>(colPatterns.Keys);
        var colCounts = new List<int> { colPatterns[cols[0]], colPatterns[cols[1]] };
        
        // Check if patterns are complementary
        for (int i = 0; i < n; i++) {
            if (rows[0][i] == rows[1][i] || cols[0][i] == cols[1][i]) {
                return -1;
            }
        }
        
        // Check count constraints
        if (Math.Abs(rowCounts[0] - rowCounts[1]) > 1 || Math.Abs(colCounts[0] - colCounts[1]) > 1) {
            return -1;
        }
        
        int CalculateMoves(List<string> patterns, List<int> counts) {
            if (n % 2 == 1) {
                int startBit = counts[0] > counts[1] ? patterns[0][0] - '0' : patterns[1][0] - '0';
                string target = "";
                for (int i = 0; i < n; i++) {
                    target += ((startBit ^ (i % 2)) + '0');
                }
                
                int moves = 0;
                for (int i = 0; i < patterns.Count; i++) {
                    if (patterns[i] != target) {
                        moves += counts[i];
                    }
                }
                return moves / 2;
            } else {
                string target1 = "", target2 = "";
                for (int i = 0; i < n; i++) {
                    target1 += (((patterns[0][0] - '0') ^ (i % 2)) + '0');
                    target2 += (((patterns[1][0] - '0') ^ (i % 2)) + '0');
                }
                
                int moves1 = 0, moves2 = 0;
                for (int i = 0; i < patterns.Count; i++) {
                    if (patterns[i] != target1) moves1 += counts[i];
                    if (patterns[i] != target2) moves2 += counts[i];
                }
                
                return Math.Min(moves1, moves2) / 2;
            }
        }
        
        int rowMoves = CalculateMoves(rows, rowCounts);
        int colMoves = CalculateMoves(cols, colCounts);
        
        return rowMoves + colMoves;
    }
}

var movesToChessboard = function(board) {
    const n = board.length;
    
    // Count row and column patterns
    const rowPatterns = new Map();
    const colPatterns = new Map();
    
    for (let i = 0; i < n; i++) {
        const rowKey = board[i].join('');
        rowPatterns.set(rowKey, (rowPatterns.get(rowKey) || 0) + 1);
        
        const colKey = board.map(row => row[i]).join('');
        colPatterns.set(colKey, (colPatterns.get(colKey) || 0) + 1);
    }
    
    if (rowPatterns.size !== 2 || colPatterns.size !== 2) {
        return -1;
    }
    
    const rows = Array.from(rowPatterns.keys());
    const rowCounts = rows.map(row => rowPatterns.get(row));
    const cols = Array.from(colPatterns.keys());
    const colCounts = cols.map(col => colPatterns.get(col));
    
    // Check if patterns are complementary
    for (let i = 0; i < n; i++) {
        if (rows[0][i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目