Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] 行列 ABC218C

Last updated at Posted at 2021-09-12

#ABC218C

S と T に含まれる # の個数が異なる場合、答えは明らかに No です。そうでない場合を考えます。

S に対して 90 度回転を何回行うか 4 通りを全探索します。回転操作を施したあとのものを改めて S と呼ぶと、平行移動で S と T を一致させられるかどうかを判定すればよいです。

両者が一致するためには、S の最も左上のマスと T の最も左上のマスが一致することが必要であり、そのようなマスを求めることで平行移動量は一意に決まるため、平行移動により実際に一致するか判定すれば十分です。

以上により $O(N^2)$ で求めることができました。

サンプルコード
def rot(S):
	return list(zip(*S[::-1]))

def find_left_top(S):
	for i in range(N):
		for j in range(N):
			if S[i][j]=='#':
				return i,j

def is_same(S,T):
	Si,Sj = find_left_top(S)
	Ti,Tj = find_left_top(T)
	offset_i = Ti-Si
	offset_j = Tj-Sj
	for i in range(N):
		for j in range(N):
			ii = i+offset_i
			jj = j+offset_j
			if 0<=ii<N and 0<=jj<N:
				if S[i][j]!=T[ii][jj]: return False
			else:
				if S[i][j]=='#': return False
	return True

N = int(input())
S = [input() for _ in range(N)]
T = [input() for _ in range(N)]

cntS = sum(1 for i in range(N) for j in range(N) if S[i][j]=='#')
cntT = sum(1 for i in range(N) for j in range(N) if T[i][j]=='#')

if cntS != cntT:
	print("No")
	exit()

for _ in range(4):
	if is_same(S,T):
		print("Yes")
		exit()
	S = rot(S)
print("No")

解法は相応の時間で思い付いたのだが、実装が難しかった。
配列での行列回転処理が未熟なのが原因である。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?