龙星尘 2023-02-26 16:40 采纳率: 42.9%
浏览 73
已结题

C++算法题(不超过普及难度)

邮票画是一幅在N×N画布上的黑白画,其中某些单元格是着墨的,而其他单元格是空白的。它可以用N×N个字符数组(1≤N≤20)来描述。如果画布在该正方形和处包含墨水,则数组第j列的第i项等于*。否则

贝西有一张她想创作的邮票画,所以农夫约翰借给她一张K×K(1≤K≤N)邮票和一张空的N×N画布。Bessie可以将印章顺时针旋转90∘,并在网格上的任何位置盖章,只要印章完全在网格内。形式上,为了盖章,Bessie选择整数i,j,使得i∈[1,N−K+1]和j∈[1、N−K+1];对于每个(i′,j′),使得1≤i′,j′≤K,画布单元(i+i′−1,j+j′−1)被涂成黑色,如果邮票在(i′、j′)处有墨水。贝西可以在冲压之间随时旋转印章。画布单元格一旦涂成黑色,它将保持黑色。

农夫约翰想知道贝西是否有可能用他的邮票创作出她想要的邮票。对于每个T(1≤T≤100)测试用例,帮助Farmer John回答这个问题。

INPUT FORMAT(输入来自终端/stdin):

输入的第一行包含T,即测试用例的数量。

每个测试用例都以一个整数N开头,后跟N行,每行包含一个s和.s字符串,表示Bessie所需的邮票绘画。下一行包含K,后面是K行,每行包含一个和.s字符串,代表Farmer John的邮票。

连续的测试用例用换行符分隔。

OUTPUT FORMAT(输出格式)(将输出打印到终端/标准输出):

对于每个测试用例,在单独的行上输出“YES”或“NO”。

样本输入:

4.

2.

**

*.

1.

*

3.

.**

.**


2.

.*

**

3.

...

.*.

...

3.

.*.

...

...

3.

**.

.**

..*

2.

.*

*.

样本输出:

YES
YES
NO
YES

在第一个测试用例中,Bessie可以执行以下冲压顺序:

在(1,1)处盖章

在(1,2)处盖章

盖章(2,1)

在第二个测试用例中,Bessie可以执行以下冲压顺序:

盖章(2,2)

盖章(2,1)

旋转90∘

旋转90∘

在(1,2)处盖章

在第三个测试用例中,不可能绘制中间单元格。

在第四个测试用例中,Bessie可以执行以下冲压顺序:

旋转90∘

在(1,1)处盖章

在(1,2)处盖章

盖章(2,2)
这是今天学校布置的题目,我不会,希望各位帮忙解答一下(用C++的算法进行),最希望给出代码和思路!

  • 写回答

1条回答 默认 最新

  • MarkHan_ 2023-02-26 17:02
    关注

    该回答引用GPTᴼᴾᴱᴺᴬᴵ
    这个问题可以用字符串匹配的方法解决。具体地,对于每个可能的盖章位置,在画布上匹配邮票图案。如果匹配成功,则返回“YES”,否则继续搜索下一个位置。如果所有可能的位置都搜索完了,返回“NO”。

    具体地说,对于每个可能的盖章位置,可以用双重循环遍历邮票和画布上的所有单元格,检查是否匹配。匹配的标准是:如果邮票图案在(i', j')处有墨水,则在画布上的(i+i'-1, j+j'-1)处也必须有墨水。如果匹配失败,则继续搜索下一个位置。如果所有的位置都尝试了,但没有找到一个匹配,那么返回“NO”。

    需要注意的是,在检查匹配时,可能会越界。因此,需要在循环中进行一些边界检查。

    下面是一个Python实现的例子:

    def rotate_stamp(stamp):
        """将邮票顺时针旋转90度"""
        rotated_stamp = []
        for i in range(len(stamp[0])):
            row = ""
            for j in range(len(stamp)-1, -1, -1):
                row += stamp[j][i]
            rotated_stamp.append(row)
        return rotated_stamp
    
    
    def check_stamp(stamp, canvas, i, j):
        """检查邮票是否可以盖到画布的位置i,j"""
        for x in range(len(stamp)):
            for y in range(len(stamp)):
                if stamp[x][y] == "*" and canvas[i+x][j+y] == ".":
                    canvas[i+x] = canvas[i+x][:j+y] + "*" + canvas[i+x][j+y+1:]
                elif stamp[x][y] == "*" and canvas[i+x][j+y] == "*":
                    return False
        return True
    
    
    def solve(stamp, canvas, n, k):
        """尝试在画布上盖邮票"""
        for i in range(n-k+1):
            for j in range(n-k+1):
                for _ in range(4):
                    if check_stamp(stamp, canvas, i, j):
                        return True
                    stamp = rotate_stamp(stamp)
        return False
    
    
    t = int(input())
    for _ in range(t):
        n = int(input())
        canvas = []
        for _ in range(n):
            row = input().strip()
            canvas.append(row)
        k = int(input())
        stamp = []
        for _ in range(k):
            row = input().strip()
            stamp.append(row)
        for _ in range(3):
            stamp = rotate_stamp(stamp)
            if solve(stamp, canvas, n, k):
                print("YES")
                break
        else:
            print("NO")
    
    
    

    这个代码中,rotate_stamp函数用于将邮票顺时针旋转90度。check_stamp函数用于检查邮票是否可以盖到画布的某个位置。solve函数用于尝试在画布上盖邮票,如果成功就返回True,否则返回False。在主程序中,我们读入输入,尝试将邮票盖到画布上,如果成功则输出"YES",否则输出"NO"。在尝试将邮票旋转3次后仍然无法将邮票盖到画布上,则输出"NO"。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 3月5日
  • 已采纳回答 3月5日
  • 创建了问题 2月26日

悬赏问题

  • ¥66 定制开发肯德基自动化网站下单软件
  • ¥20 vscode虚拟环境依赖包未安装
  • ¥15 odoo17关于owl开发js代码问题
  • ¥15 光纤中多普勒频移公式的推导
  • ¥15 怎么制作一个人脸识别门禁系统
  • ¥20 大华dss监控平台网络关闭登不进去
  • ¥15 请使用蚁群算法解决下列问题,并给出我完整的代码
  • ¥20 关于php录入完成后,批量更新数据库
  • ¥15 请教往复密封润滑问题
  • ¥15 cocos creator发布ios包