資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將二進位制矩陣轉換為零矩陣所需的最小翻轉次數
假設我們有一個 m x n 的二進位制矩陣 mat。一步之內，我們可以選擇一個單元格並翻轉其位及其所有四個鄰居（如果存在）。我們必須找到將 mat 轉換為零矩陣所需的最小步數。如果沒有解決方案，則返回 -1。
因此，如果給定的輸入類似於 [[0,0], [0,1]]，則更改將類似於 -
所以我們需要 3 步，輸出將是 3。
為了解決這個問題，我們將遵循以下步驟 -
- n := 行數，m := 列數，x := 0
- 初始化 i := 0，當 i < n 時，更新（i 增加 1），執行 -
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- x := x + 將 mat[i][j] 的值左移 (i * m) + j) 次
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- 定義一個包含 2^(n * m) 個單元格的陣列 dp，並將其全部填充為 -1
- dp[x] := 0
- 定義一個佇列 q
- 將 x 插入 q
- 當 (q 不為空) 時，執行 -
- current := q 的第一個元素，從 q 中刪除該元素
- 如果 current 等於 0，則 -
- 返回 dp[current]
- 初始化 i := 0，當 i < n 時，更新（i 增加 1），執行 -
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- temp := current
- temp := temp XOR 2^ (i * m) + j)
- 初始化 k := 0，當 k < 4 時，更新（k 增加 1），執行 -
- ni := i + dir[k][0]
- nj := j + dir[k][1]
- 如果 ni < 0 或 nj < 0 或 ni >= n 或 nj >= m，則 -
- 忽略以下部分，跳到下一次迭代
- temp := temp XOR 2^ (ni * m) + nj)
- 如果 dp[temp] 等於 -1，則 -
- dp[temp] := dp[current] + 1
- 將 temp 插入 q
- 初始化 j := 0，當 j < m 時，更新（j 增加 1），執行 -
- 返回 -1
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
int x = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
x += (mat[i][j] << ((i * m) + j));
}
}
vector < int > dp(1 << (n*m), -1);
dp[x] = 0;
queue <int> q;
q.push(x);
while(!q.empty()){
int current = q.front();
q.pop();
if(current == 0)return dp[current];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int temp = current;
temp ^= (1 << ((i *m) + j));
for(int k = 0; k < 4; k++){
int ni = i + dir[k][0];
int nj = j + dir[k][1];
if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
temp ^= (1 << ((ni *m) + nj));
}
if(dp[temp] == -1){
dp[temp] = dp[current] + 1;
q.push(temp);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0},{0,1}};
cout << (ob.minFlips(v));
}輸入
{{0,0},{0,1}}輸出
3
更新於: 2020年6月2日
132 次檢視
廣告