首页 > 试题广场 >

画家小Q

[编程题]画家小Q

热度指数：5287 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

画家小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

输出

说明

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

算法知识视频讲解

Python

TER

90% 通过率？ 为什么啊

python 递归

n,m = map(int, input().split(" "))
L = []
for i in range(n):
    L.append(list(input().strip()))
def change(L, coordinate, target):
    n, m = len(L), len(L[0])
    i, j = coordinate
    L[i][j] = target
    if target == 'B':
        # left_dowm
        count = 1
        for r in range(i, min(n, i + j + 1)):
            l = i + j - r
            if L[r][l] == 'B':
                L[r][l] = 'X'
            elif L[r][l] == 'G':
                L[r][l] = 'Y'
            else:
                break
    elif target == 'Y':
        # right_down
        count = 1
        for r in range(i, min(n, m + i - j)):
            l = r - i + j
            if L[r][l] == 'Y':
                L[r][l] = 'X'
            elif L[r][l] == 'G':
                L[r][l] = 'B'
            else:
                break
    else:
        change(L, coordinate, 'B')
        change(L, coordinate, 'Y')
        count = 2
    return count
def painter(L):
    n, m = len(L), len(L[0])
    for i in range(n):
        for j in range(m):
            target = L[i][j]
            if target != 'X':
                count = change(L, [i, j],target)
                return count + painter(L)
    else:return 0
print(painter(L))

编辑于 2020-03-31 23:02:36 回复(0)

Python

Offer+1行不行

import sys


class MinStep():
    def __init__(self, matrix, N, M):
        self.matrix = matrix
        self.N = N
        self.M = M
        self.count = 0
    
    
    def minus_Y(self, n, m):
        self.count += 1
        while n < self.N and m < self.M:
            if self.matrix[n][m] == 'Y':
                self.matrix[n][m] = 'X'
            elif self.matrix[n][m] == 'G':
                self.matrix[n][m] = 'B'
            else:
                break
            n += 1
            m += 1
    
    
    def minus_B(self, n, m):
        self.count += 1
        while n < self.N and m >= 0:
            if self.matrix[n][m] == 'B':
                self.matrix[n][m] = 'X'
            elif self.matrix[n][m] == 'G':
                self.matrix[n][m] = 'Y'
            else:
                break
            n += 1
            m -= 1
    
    
    def get_min_step(self):
        for n in range(self.N):
            for m in range(self.M):
                if self.matrix[n][m] == 'Y':
                    self.minus_Y(n, m)
                elif self.matrix[n][m] == 'B':
                    self.minus_B(n, m)
                elif self.matrix[n][m] == 'G':
                    self.minus_Y(n, m)
                    self.minus_B(n, m)
        return self.count


if __name__ == '__main__':
    n_m = list(map(int, sys.stdin.readline().strip().split()))
    n, m = n_m[0], n_m[1]
    matrix = []
    for _ in range(n):
        matrix.append(list(sys.stdin.readline().strip()))
    MS = MinStep(matrix, n, m)
    print(MS.get_min_step())

发表于 2019-04-08 18:35:03 回复(1)