資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的棋盤轉換
假設我們有一個 N x N 的棋盤，其中只包含 0 和 1。現在在每次移動中，我們可以交換任意兩行，或任意兩列。我們必須找到將棋盤轉換為“棋盤”所需的最小移動次數。如果不存在解決方案，則返回 -1。
因此，如果輸入類似於 -
則輸出將為 2，因為在第一次移動中交換前兩列，然後棋盤將類似於 -
然後交換第二行和第三行 -
這是棋盤
為了解決這個問題，我們將遵循以下步驟 -
- n := b 的大小
- 初始化 i := 0，當 i < n 時，更新（i 加 1），執行 -
- 初始化 j := 0，當 j < n 時，更新（j 加 1），執行 -
- 如果 b[0, 0] XOR b[0, j] XOR b[i, 0] XOR b[i, j] 不為零，則 -
- 返回 -1
- 如果 b[0, 0] XOR b[0, j] XOR b[i, 0] XOR b[i, j] 不為零，則 -
- 初始化 j := 0，當 j < n 時，更新（j 加 1），執行 -
- rowSum := 0, colSum := 0, rowSwap := 0, colSwap := 0
- 初始化 i := 0，當 i < n 時，更新（i 加 1），執行 -
- rowSum := rowSum + b[i, 0], colSum := colSum + b[0, i]
- 當 rowSwap + b[i, 0] 等於 i mod 2 時，rowSwap := true，
- 當 colSwap + b[0, i] 等於 i mod 2 時，colSwap := true
- 如果 rowSum 不等於 n / 2 且 rowSum 不等於 (n + 1) / 2，則 -
- 返回 -1
- 如果 colSum 不等於 n / 2 且 colSum 不等於 (n + 1) / 2，則 -
- 返回 -1
- 如果 n mod 2 等於 1，則 -
- 如果 colSwap mod 2 不為零，則 -
- colSwap := n - colSwap
- 如果 rowSwap mod 2 不為零，則 -
- rowSwap := n - rowSwap
- 如果 colSwap mod 2 不為零，則 -
- 否則
- colSwap := colSwap 和 n - colSwap 的最小值
- rowSwap := rowSwap 和 n - rowSwap 的最小值
- 返回 (rowSwap + colSwap) / 2
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int movesToChessboard(vector<vector<int>>& b) {
int n = b.size();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) return -1;
}
}
int rowSum = 0;
int colSum = 0;
int rowSwap = 0;
int colSwap = 0;
for(int i = 0; i < n; i++){
rowSum += b[i][0];
colSum += b[0][i];
rowSwap += b[i][0] == i % 2;
colSwap += b[0][i] == i % 2;
}
if(rowSum != n/2 && rowSum != (n + 1)/2)return -1;
if(colSum != n/2 && colSum != (n + 1)/2)return -1;
if(n % 2 == 1){
if(colSwap % 2) colSwap = n - colSwap;
if(rowSwap % 2) rowSwap = n - rowSwap;
}else{
colSwap = min(colSwap, n - colSwap);
rowSwap = min(rowSwap, n - rowSwap);
}
return (rowSwap + colSwap)/2;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};
cout << (ob.movesToChessboard(v));
}輸入
{{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};輸出
2
更新於: 2020年6月2日
433 次檢視
廣告