时间戳

首页 > 解决方案 > 计算清除图片所需的最少点击次数

c++ - 计算清除图片所需的最少点击次数

问题描述

我一直在尝试为 Cs-academy 网站的竞争编码问题编写一个程序。

问题如下：

假设我们正在浏览一堆黑白图片，突然，一个古怪的想法出现在你的脑海中——需要多少次点击才能将所有白色像素转换为黑色并使用画笔清除图片？因此，我们扫描了几张图片并将其转换为二进制数据。二进制图片的每个像素现在由一个整数表示，0 表示黑色像素，1 表示白色像素。

要修改一张图片，我们每次只能使用三种画笔中的一种：

+(加号) - 使用时，当前像素的左、上、右、下的像素也用相同的颜色着色。

x(cross) - 使用时，当前像素的左上角、右上角、右下角和左下角的像素也用相同的颜色着色。

*(star) - 使用时，当前像素周围的所有 9 个像素也以相同颜色着色。

（这里有一个插图：https ://publicmedia1.csacademy.com/public/1507909042-2157482298.png ）

这些画笔中的每一个在使用时都会递归地工作。所以如果你给一个像素着色，它的邻居会被着色，然后是邻居的邻居，等等。

我们的任务是计算您为清除图片而必须使用每个画笔执行的最少点击次数：首先我们必须计算仅使用 + 画笔清除图片所需的最少点击次数，然后计算最小值仅使用 x 画笔清除图片所需的点击次数，最后计算仅使用 * 画笔清除图片所需的最小点击次数。

输入以单个数字 t (1≤t≤100) 开始，它表示要处理的图片数量。每个测试用例都以一行开头，其中包含 2 个空格分隔的整数 w 和 h，分别表示图片的宽度和高度（以像素为单位）（1≤w，h≤1001）。接下来会有 h 行表示图片每一行的 w 个像素值（0 或 1）。

对于每个测试用例输出，3 个空格分隔的整数表示清除三个画笔中的每个画笔所需的最少点击次数：+、x 和 *。

我写了一个递归计算的程序 - 使用单独的函数 - 3个选项中的每一个的计数：

#include <iostream>
using namespace std;

const int N = 101;
int mat[N][N];

void pluse(int mat[][N],int h , int w, int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]==0)
        return;
    mat[i][j]=0;
    pluse(mat,h,w,i+1,j);
    pluse(mat,h,w,i-1,j);
    pluse(mat,h,w,i,j+1);
    pluse(mat,h,w,i,j-1);

}
void cross(int mat[][N],int h, int w,int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]==0)
        return;
    mat[i][j]=0;
    cross(mat,h,h,i+1,j+1);
    cross(mat,h,w,i-1,j-1);
    cross(mat,h,w,i-1,j+1);
    cross(mat,h,w,i+1,j-1);
}
void star(int mat[][N],int h, int w,int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]==0)
        return;
    mat[i][j]=0;
    star(mat,h,w,i+1,j);
    star(mat,h,w,i-1,j);
    star(mat,h,w,i,j+1);
    star(mat,h,w,i,j-1);
    star(mat,h,w,i+1,j+1);
    star(mat,h,w,i-1,j-1);
    star(mat,h,w,i-1,j+1);
    star(mat,h,w,i+1,j-1);
}


int ans1(int mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]==1){
                pluse(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}

int ans2(int mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]==1){
                cross(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}

int ans3(int mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]==1){
                star(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}
int main()
{

    int t=1,h,w;
    int mat1[N][N],mat2[N][N],mat3[N][N];
    cin>>t;
    while(t--)
    {
        cin>>w>>h;

           for(int i = 0;i<h;i++){
            for(int j = 0;j<w;j++){
                cin>>mat1[i][j];
                mat2[i][j]=mat3[i][j]=mat1[i][j];
            }
        }
        cout<<ans1(mat1,h,w)<<" "<<ans2(mat2,h,w)<<" "<<ans3(mat3,h,w)<<endl;
    }
    return 0;

}

但是，我的程序无法给出正确的输出，我也无法检测到原因。

例如，对于以下输入：

1011001
0010001
0001000
0000001
26 13
11111111111111111111111111
11111100111111111100111111
11110001111100111110001111
11000001111000011110000011
10000000111000011100000001
10000000000000000000000001
00000000000000000000000000
00000000000000000000000000
10000000000000000000000001
10000110001000010001100001
11001111111100111111110011
11100111111100111111100111
11111111111111111111111111

我得到输出：

111
000

而正确的输出实际上是：

5 6 4
2 18 2

更新：

我这样重写了我的代码：

#include <iostream>

using namespace std;

const int N = 1001;
char mat[N][N];

void pluse(char mat[][N],int h , int w, int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]=='0')
        return;
    mat[i][j]='0';
    pluse(mat,h,w,i+1,j);
    pluse(mat,h,w,i-1,j);
    pluse(mat,h,w,i,j+1);
    pluse(mat,h,w,i,j-1);

}
void cross(char mat[][N],int h, int w,int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]=='0')
        return;
    mat[i][j]='0';
    cross(mat,h,h,i+1,j+1);
    cross(mat,h,w,i-1,j-1);
    cross(mat,h,w,i-1,j+1);
    cross(mat,h,w,i+1,j-1);
}
void star(char mat[][N],int h, int w,int i,int j)
{
    if(i<0||j<0||i>=h||j>=w||mat[i][j]=='0')
        return;
    mat[i][j]='0';
    star(mat,h,w,i+1,j);
    star(mat,h,w,i-1,j);
    star(mat,h,w,i,j+1);
    star(mat,h,w,i,j-1);
    star(mat,h,w,i+1,j+1);
    star(mat,h,w,i-1,j-1);
    star(mat,h,w,i-1,j+1);
    star(mat,h,w,i+1,j-1);
}


int ans1(char mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]=='1'){
                pluse(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}

int ans2(char mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]=='1'){
                cross(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}

int ans3(char mat[][N],int h , int w)
{
    int count = 0;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(mat[i][j]=='1'){
                star(mat,h,w,i,j);
                count++;
            }
        }
    }
    return count;
}
int main()
{

    int t=1,h,w;
    cin>>t;
    while(t--)
    {
        cin>>w>>h;
        {
           char mat1[N][N],mat2[N][N],mat3[N][N];


           for(int i = 0;i<h;i++){
            for(int j = 0;j<w;j++){
                cin>>mat1[i][j];
                mat2[i][j]=mat1[i][j];
                mat3[i][j]=mat1[i][j];
            }
        }
        cout<<ans1(mat1,h,w)<<" "<<ans2(mat2,h,w)<<" "<<ans3(mat3,h,w)<<endl;
        }
    }
    return 0;

}

但是，对于上述输入，我得到了输出

5 6 4
2 43 2

这是不正确的，因为正确的应该是：

5 6 4
2 18 2

标签： c++

解决方案

您没有正确读取输入。

当你运行时cin>>mat1[i][j]，因为mat1[i][j]是一个整数，整行输入都将被读入。所以对于第一个（小）示例，mat[0][0]将具有值 1011001（一百万、一万一千和一）。您应该做的是一次读取输入矩阵一个字符，然后在矩阵中存储一个适当的值，注意正确处理换行符（并检查输入中的错误）。

另一个问题是您不输出任何空格，因此所有三个数字一起运行以形成一个更大的数字。

推荐阅读