AtCoder Beginner Contest 375 C题 (python解)
Panasonic Programming Contest 2024(AtCoder Beginner Contest 375)C - Spiral Rotation(python解)**
原题链接:
[(https://atcoder.jp/contests/abc375/tasks/abc375_c)]
题目简述:
这道题要求对一个 N x N 的网格进行特定的螺旋旋转操作,而这个 N 总是偶数。在这里,网格中的每个单元格可以是黑色(用 #
表示)或白色(用 .
表示)。我们需要根据题目的描述,通过一系列的操作最终输出网格的颜色状态。
思路:
对于 i =1
到 N/2
,在每个 i
进行 (i +1) %4
次旋转。也就是说:i =1
时执行2 次旋转 - i =2
时执行3 次旋转 - i =3
时执行0 次旋转 - i =4
时执行1 次旋转 -依此类推……
旋转的定义是将相应的颜色值从一个位置移动到另一个位置。
python代码
def func(N, i, A):
r = N-1-i#计算当前层的右边界
for j in range(i,r):# 执行四个位置的颜色值交换,实现螺旋旋转
(A[j][r], A[r][N-1-j], A[N-1-j][i], A[i][j]) = (A[i][j], A[j][r], A[r][N-1-j], A[N-1-j][i])
def main():
N = int(input())
A = [list(input()) for _ in range(N)]#读取网格数据
for i in range(N//2):# 遍历每一个层次,从外层到内层(共 N/2 层)
for j in range((i+1)%4):# 根据当前层数 i计算旋转次数
func(N, i, A)
print("\n".join("".join(i) for i in A))# 输出最终的网格状态,将每一行转换为字符串,并用换行符连接
main()
自定义func(N, i, A)
函数:
-
i
是当前层的左边界,r
是右边界。
通过一个循环,将当前层的四个位置的颜色值进行交换,实现旋转。 -
逻辑如下:
A[i][j]
(左上)交换到A[j][r]
(右上)A[j][r]
交换到A[r][N-1-j]
(右下)A[r][N-1-j]
交换到A[N-1-j][i]
(左下)A[N-1-j][i]
交换到A[i][j]
(左上)
最后进行复杂度分析:
每一层的旋转操作是 O(N/2),因为每层的旋转交换只涉及该层的元素。