数据结构
网络
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 次查看
广告