开心消消乐题解

这篇具有很好参考价值的文章主要介绍了开心消消乐题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

给定一个 N M 列的二维矩阵,矩阵中每个位置的数字取值为 0 1,矩阵示例如:

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

输入

第一行输入两个整数,分别表示矩阵的行数 N 和列数 M,取值范围均为 [1,100]

接下来 N 行表示矩阵的初始值,每行均为 M 个数,取值范围 [0,1]

输出

输出一个整数,表示最少需要点击的次数

示例一

输入

3 3
1 0 1
0 1 0
1 0 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;

 代码:

/*
给定一个 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包