标签搜索

目 录CONTENT

文章目录

腾讯---画家小Q.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 5 阅读 / 2,180 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

画家小Q.md
date: 2021-08-22 12:10:07.812
updated: 2021-08-22 12:10:07.812
url: /2021/08/22/腾讯---画家小qmd
categories:
tags:

腾讯---画家小Q

@[toc]

一、题目描述

画家小Q又开始他的艺术创作。小Q拿出了一块有NxM像素格的画板, 画板初始状态是空白的,用'X'表示

小Q有他独特的绘画技巧,每次小Q会选择一条斜线, 如果斜线的方向形如'/',即斜率为1,小Q会选择这条斜线中的一段格子,都涂画为蓝色,用'B'表示;

如果对角线的方向形如'\',即斜率为-1,小Q会选择这条斜线中的一段格子,都涂画为黄色,用'Y'表示

如果一个格子既被蓝色涂画过又被黄色涂画过,那么这个格子就会变成绿色,用'G'表示。

小Q已经有想画出的作品的样子, 请你帮他计算一下他最少需要多少次操作完成这幅画。

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数N和M(1 <= N, M <= 50), 表示画板的长宽。
接下来的N行包含N个长度为M的字符串, 其中包含字符'B','Y','G','X',分别表示蓝色
,黄色,绿色,空白。整个表示小Q要完成的作品。

输出描述:

输出一个正整数, 表示小Q最少需要多少次操作完成绘画。

输入例子1:

4 4
YXXB
XYGX
XBYY
BXXY

输出例子1:

3

例子说明1:

XXXX
XXXX
XXXX
XXXX
->
YXXX
XYXX
XXYX
XXXY
->
YXXB
XYBX
XBYX
BXXY
->
YXXB
XYGX
XBYY
BXXY

二、分析

这道题很简单,千万不要被题给吓住了

  •  这道题给了着色的方法和目标的图案,我们首先肯定会想到把一个空白的画板(全为‘X’)经过n次涂色,转变为目标图案,如果你这样想,你就入坑了,因为你根本不知道每次涂多少个块(需要遍历计算),这样就非常麻烦
  •  所以需要转变思想,既然画板初始值全为‘X’,目标图案已经给你了,那么我们只需要计算从目标图案转变为空白画板(全为‘X’)最少的次数即可
  •  我们怎么把目标图案转变为空白画板(全为‘X’)呢?
  •  转换的方法和涂色方法完全相反即可:
    1.从(0,0)位置开始遍历
    2.如果遍历到(i,j)位置为B——>则以该点继续向左下方(i+1,j-1)右上方(i-1,j+1)遍历时,遇到将B置为X,遇到G置为(消除B)置为Y
count++;

3.如果遍历到(i,j)位置为Y——>则以该点继续向左上方(i-1,j-1)和右下方(i+1,j+1)遍历时,遇到将Y置为X,遇到G置为(消除Y)置为B

count++;

4.如果遍历到(i,j)位置为G——>则分别执行2,3

三、代码

#include <iostream>
#include <vector>
using namespace std;

//用户输入的目标图案
vector<vector<char>> str;
//行列
int n,m;

//遇到Y的处理
void dfs_Y(int x,int y)
{
	//判断下标是否越界并且是字符Y或G
    if(x >= 0 && x < n && y >= 0 && y < m && (str[x][y] == 'Y' || str[x][y] == 'G'))
    {
        if(str[x][y] == 'G')
            str[x][y] = 'B';
        else
            str[x][y] = 'X';
        //往左上和右下递归判断
        dfs_Y(x - 1,y - 1);
        dfs_Y(x + 1,y + 1);
    }
    return ;
}

//遇到字符B的处理
void dfs_B(int x,int y)
{
	//判断下标是否越界并且是B或者G字符
    if(x >= 0 && x < n && y >= 0 && y < m && (str[x][y] == 'B' || str[x][y] == 'G'))
    {
        if(str[x][y] == 'G')
            str[x][y] = 'Y';
        else
            str[x][y] = 'X';
        //递归往右上和左下判断
        dfs_B(x + 1,y - 1);
        dfs_B(x - 1,y + 1);
    }
    return ;
}

int main()
{
    int cnt=0;
    cin>>n>>m;
    
    str = vector<vector<char>>(n,vector<char>(m));
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            cin>>str[i][j];
        }
    }

	//循环遍历目标图案
    for(int i = 0;i < n;i++)
    {
       for(int j = 0;j < m;j++)
       {
           if(str[i][j] == 'Y')
           {
               dfs_Y(i,j);
               cnt++;
           }
           else if(str[i][j] == 'B')
           {
               dfs_B(i,j);
               cnt++;
           }
           else if(str[i][j] == 'G')
           {
               dfs_Y(i,j);
               str[i][j]='B';
               dfs_B(i,j);
               cnt += 2;
           }
       }
    }
    cout<<cnt<<endl;
    return 0;
}
0

评论区