题目描述:
给定一个 N 行 M 列的二维矩阵,矩阵中每个位置的数字取值为 0 或 1,矩阵示例如:
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0,规则如下:
- 当点击一个 1 时,该 1 被反转为 0,同时相邻的上、下、左、右,以及左上、左下、右上、右下 8 个方向的 1 (如果存在 1)均会自动反转为 0;
-
进一步地,一个位置上的 1 被反转为 0 时,与其相邻的 8 个方向的 1 (如果存在 1)均会自动反转为 0;
按照上述规则示例中的矩阵只最少需要点击 2 次后,所有均值 0 。请问,给定一个矩阵,最少需要点击几次后,所有数字均为 0?
输入
第一行输入两个整数,分别表示矩阵的行数 N 和列数 M,取值范围均为 [1,100]
接下来 N 行表示矩阵的初始值,每行均为 M 个数,取值范围 [0,1]
输出
输出一个整数,表示最少需要点击的次数
示例一
输入
3 3
1 0 1
0 1 0
1 0 1
输出
1
分析:
如表所示,表的元素其余为零
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
6个1,共有6*5*4*3*2*1=n!反转的选择。由于感染式反转,所以实际可能比这更少==>6*(k1*k2*..ki),比如k1可能是5、4、3、2、1、0,k2对应可能是4、3、2、1、0(k1为4时)...
回溯递归解题:
第一层:
循环查找原表,
找到1个后,计数器cnt加1;创建一个新表,反转这个1;传递新表给第二层;cnt+=第二层的返回值
如果cnt《min,则min=cnt;即选择第一层需要最少的反转次数那种选择。
返回min
第二层:同第一层的操作,“原表”即”新表“;
…
直到表中没有1;文章来源:https://www.toymoban.com/news/detail-479111.html
代码:
/*
给定一个 N 行 M 列的二维矩阵,矩阵中每个位置的数字取值为 0 或 1,矩阵示例如:
4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0,规则如下:
1. 当点击一个 1 时,该 1 被反转为 0,同时相邻的上、下、左、右,以及左上、左下、右上、右下 8 个方向的 1 (如果存在 1)均会自动反转为 0;
2. 进一步地,一个位置上的 1 被反转为 0 时,与其相邻的 8 个方向的 1 (如果存在 1)均会自动反转为 0;
按照上述规则示例中的矩阵只最少需要点击 2 次后,所有均值 0 。请问,给定一个矩阵,最少需要点击几次后,所有数字均为 0?
*/
#include <iostream>
#include <vector>
using namespace std;
void clear_one(vector<vector<int>> &data, int i, int j)
{
int rs, cs;
if(data.empty())
{
cout << "error 2." << endl;
return;
}
rs = data.size();
cs = data[0].size();
if(data[i][j] != 1)
{
return;
}
data[i][j] = 0;
if(i-1 >= 0)
{
clear_one(data, i-1, j);
}
if(i+1 < rs)
{
clear_one(data, i+1, j);
}
if(j-1 >= 0)
{
clear_one(data, i, j-1);
}
if(j+1 < cs)
{
clear_one(data, i, j+1);
}
if(i-1 >= 0 && j-1 >= 0)
{
clear_one(data, i-1, j-1);
}
if(i-1 >= 0 && j+1 < cs)
{
clear_one(data, i-1, j+1);
}
if(i+1 < rs && j-1 >= 0)
{
clear_one(data, i+1, j-1);
}
if(i+1 < rs && j+1 < cs)
{
clear_one(data, i+1, j+1);
}
}
int pop(vector<vector<int>> &data)
{
int cnt = 0;
int min = data.size();
int rs, cs;
bool flag = false;
if(data.empty())
{
cout << "error." << endl;
return -1;
}
rs = data.size();
cs = data[0].size();
for(int i = 0; i != rs; i++)
{
for(int j = 0; j != cs; j++)
{
if(data[i][j] == 1)
{
vector<vector<int>> new_data(data);
clear_one(new_data, i, j);
cnt = 1 + pop(new_data);
flag = true;
if(cnt < min)
{
min = cnt;
}
}
}
}
if(flag)
{
return min;
}
return 0;
}
int main()
{
int row_size;
int column_size;
vector<vector<int>> data;
cin >> row_size >> column_size;
for(int i = 0; i != row_size; i++)
{
vector<int> tmp;
for(int j = 0; j != column_size; j++)
{
int n;
cin >> n;
tmp.push_back(n);
}
data.push_back(tmp);
}
cout << "load data finished!." << endl;
cout << pop(data) << endl;
}
文章来源地址https://www.toymoban.com/news/detail-479111.html
到了这里,关于开心消消乐题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!