資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：計算將二進位制矩陣轉換為零矩陣所需的操作次數
假設我們有一個二進位制矩陣。現在考慮一個操作，其中我們取一個單元格並翻轉它及其所有相鄰單元格（上、下、左、右）。我們必須找到使矩陣僅包含 0 的所需的最少操作次數。如果沒有解決方案，則返回 -1。
因此，如果輸入類似於
| 0 | 0 |
| 1 | 0 |
則輸出將為 3。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為 4 x 2 的陣列 dir：={{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
- const int inf = 10^6
- 定義一個函式 getPos()，它將接收 i、j，
- 返回 i * c + j
- 定義一個函式 getCoord()，它將接收 x
- 定義一個 pair ret
- ret[0] := x / c
- ret[1] := x mod c
- 返回 ret
- 從主方法執行以下操作
- mask := 0
- r := 矩陣的行數
- c := 矩陣的列數
- last := r * c
- 初始化 i := 0，當 i < r 時，更新（i 增加 1），執行
- 初始化 j := 0，當 j < c 時，更新（j 增加 1），執行
- mask := mask XOR (matrix[i, j] * 2^getPos(i, j))
- 初始化 j := 0，當 j < c 時，更新（j 增加 1），執行
- 定義一個大小為 512 的陣列 dist 並用 -1 填充
- 定義一個佇列 q
- 將 mask 插入到 q 中
- dist[mask] := 0
- 當 (q 不為空) 時，執行
- mask := q 的第一個元素
- 從 q 中刪除元素
- 初始化 i := 0，當 i < last 時，更新（i 增加 1），執行
- 定義一個 pair coord
- x := coord[0]
- y := coord[1]
- nmask := mask
- nmask := nmask XOR 2^i
- 初始化 k := 0，當 k < 4 時，更新（k 增加 1），執行
- nx := x + dir[k, 0]
- ny := y + dir[k, 1]
- 如果 nx 和 ny 不在矩陣範圍內，則
- 忽略以下部分，跳過到下一個迭代
- pos := getPos(nx, ny)
- nmask := nmask XOR (2^pos)
- 如果 dist[nmask] 等於 -1 或 dist[nmask] > dist[mask] + 1，則
- dist[nmask] := dist[mask] + 1
- 將 nmask 插入到 q 中
- 返回 dist[0]
讓我們看看以下實現以更好地理解：
示例
#include
using namespace std;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;
int getPos(int i, int j){
return i * c + j;
}
pair getCoord(int x){
pair ret;
ret.first = x / c;
ret.second = x % c;
return ret;
}
int solve(vector>& matrix) {
int mask = 0;
r = matrix.size();
c = r ? matrix[0].size() : 0;
last = r * c;
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
mask ^= (matrix[i][j] << getPos(i, j));
}
}
vector dist(1 << 9, -1);
queue q;
q.push(mask);
dist[mask] = 0;
while(!q.empty()){
mask = q.front();
q.pop();
for(int i = 0; i < last; i++){
pair coord = getCoord(i);
int x = coord.first;
int y = coord.second;
int nmask = mask ;
nmask ^= (1 << i);
for(int k = 0; k < 4; k++){
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx < 0 || nx >= r || ny < 0 || ny >= c)
continue;
int pos = getPos(nx, ny);
nmask ^= (1 << pos);
}
if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
dist[nmask] = dist[mask] + 1;
q.push(nmask);
}
}
}
return dist[0];
}
int main(){
vector> v = {{0, 0},{1, 0}};
cout << solve(v);
}輸入
{{0, 0},{1, 0}}輸出
3
更新於： 2020年12月3日
98 次檢視
廣告