Problem:


写真に写っている景色は?

 A 君は会津に観光にやってきました。宿泊したホテルの窓からは会津盆地が一望できます。景色を眺めていると、床に写真の切れ端が落ちているのに気がつきました。どうやら窓から外の景色を撮ったようです。「どの辺りを撮ったのかな」と、A 君は窓の外の景色と写真が同じ大きさになるように写真をかざして、写真と窓の外の景色が一致する場所を探し始めました。

 それでは、A 君がやっていることをコンピュータでやってみましょう。窓の外の景色を n &times; n マスの正方形に分割します (n を景色の大きさと呼びます)。各マスには、そのマスの画像の情報を表す 0 以上の整数が書かれています。マスの位置は座標 (x, y) で表します。各マスの座標は以下の通りになります。

 写真の切れ端は、m &times; m マスの正方形で表されます (m を写真の切れ端の大きさと呼びます) 。この正方形の中で、切れ端の部分のマスには画像の情報が、切れ端に含まれない部分のマスには -1 が書かれています。たとえば、下図では、色が塗られている部分が実際の写真の切れ端の形を表しています。切れ端に穴が開いていることはありますが、必ず 1 つにつながっています。 (0 以上の値をもつマスが頂点だけで接しているときは、つながっていないものとみなします。) また、値 -1 のマスが縦または横 1 列に端から端まで並ぶことはありません。

  窓から見える景色の中で、写真の切れ端を 0、90、180、270 度回転させたいずれかと一致する領域を探します。たとえば、景色が下図のように表わせるとき、上図の切れ端を反時計回りに90 度回転させると、色が塗られた領域に一致します。

 窓から見える景色と写真の切れ端の情報を入力とし、景色の中で、切れ端を 0、90、180、270 度回転させたいずれかと一致する領域の最も上端に近いマスのうち、最も左端に近いマスの座標を出力するプログラムを作成してください。

 一致する領域が複数ある場合は、それらの領域内にあるマスの中で、最も上端に近いマスのうち、最も左端に近いマスの座標を出力してください。一致する領域がないときは、NA と出力します。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

n m
w11 w12 ... w1n
w21 w22 ... w2n
:
wn1 wn2 ... wnn
p11 p12 ... p1m
p21 p22 ... p2m
:
pm1 pm2 ... pmm

1 行目にn, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 50, m ≤ n) が与えられます。

続く n 行に窓から見える景色の情報 wij (0 ≤ wij ≤ 15)、続く m 行に写真の切れ端のデータの情報 pij (-1 ≤ pij ≤ 15) が与えられます。

データセットの数は 100 を超えません。

Output

入力データセットごとに、マスの位置の座標または NA を１行に出力します。

Sample Input

8 4
2 1 3 1 1 5 1 3
2 3 2 4 1 0 2 1
0 3 1 2 1 1 4 2
1 2 3 2 1 1 5 4
0 2 0 1 1 3 2 1
1 3 1 2 2 4 3 2
5 1 2 1 4 1 1 5
4 1 1 0 1 2 2 1
2 -1 -1 -1
0 3 -1 -1
-1 2 2 4
-1 1 -1  1
5 3
1 0 2 3 5
2 3 7 2 1
2 5 4 2 2
8 9 0 3 3
3 6 0 4 7
-1 -1 2
-1 3 5
0 4 -1
0 0

Output for the Sample Input

4 2
NA



Sample input:
8 4
2 1 3 1 1 5 1 3
2 3 2 4 1 0 2 1
0 3 1 2 1 1 4 2
1 2 3 2 1 1 5 4
0 2 0 1 1 3 2 1
1 3 1 2 2 4 3 2
5 1 2 1 4 1 1 5
4 1 1 0 1 2 2 1
2 -1 -1 -1
0 3 -1 -1
-1 2 2 4
-1 1 -1  1
5 3
1 0 2 3 5
2 3 7 2 1
2 5 4 2 2
8 9 0 3 3
3 6 0 4 7
-1 -1 2
-1 3 5
0 4 -1
0 0


Sample output:
4 2
NA

Submission status: Accepted

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                else:
                    return
    else:
        if ans is None:
            ans = coordinate
        elif coordinate[1] < ans[1]:
            ans = coordinate
        elif coordinate[1] == ans[1]:
            if coordinate[0] < ans[0]:
                ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    ans = None
    main(piece, 1)
    if ans:
        print ans[0], ans[1]
    else:
        print 'NA'

Submission status: Accepted

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)
    else:
        if ans:
            print ans[0], ans[1]
        else:
            print 'NA'

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                        if ans:
                            if coordinate[1] > ans[1]:
                                return
                            elif coordinate[1] == ans[1]:
                                if coordinate[0] > ans[0]:
                                    return
                else:
                    return
    else:
        ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    ans = None
    main(piece, 1)

Submission status: Accepted

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)
    else:
        if ans:
            print ans[0], ans[1]
        else:
            print 'NA'

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                else:
                    return
    else:
        if ans is None:
            ans = coordinate
        elif coordinate[1] < ans[1]:
            ans = coordinate
        elif coordinate[1] == ans[1]:
            if coordinate[0] < ans[0]:
                ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    ans = None
    main(piece, 1)

Submission status: Accepted

Solution code:
def getxy(P,x,y,ans):
	for dy in range(m):
		for dx in range(m):
			if P[dy][dx] > -1:
				xy = [x+dx+1,y+dy+1]
				if ans == "NA" or xy[1] < ans[1] or (xy[1] == ans[1] and xy[0] < ans[0]):
					return xy
				else:
					return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		S = [map(int,raw_input().split()) for i in range(n)]
		P = [map(int,raw_input().split()) for i in range(m)]

		ans = "NA"
		for rot in range(4):
			if S == P:
				ans = getxy(P,0,0,ans)
			for y in range(n-m+1):
				for x in range(n-m+1):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if P[dy][dx] > -1 and S[y+dy][x+dx] - P[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(P,x,y,ans)
						break
				if flag == 0: break
			P = [[P[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print ans if ans == "NA" else " ".join(map(str,ans))
	except:
		pass

Submission status: Accepted

Solution code:
def getxy(P,x,y,ans):
	for dy in range(m):
		for dx in range(m):
			if P[dy][dx] > -1:
				xy = [x+dx+1,y+dy+1]
				if xy[1] < ans[1] or (xy[1] == ans[1] and xy[0] < ans[0]):
					return xy
				else:
					return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		S = [map(int,raw_input().split()) for i in range(n)]
		P = [map(int,raw_input().split()) for i in range(m)]
		ans = [n+1,n+1]
		for rot in range(4):
			for y in range(min(ans[1],n-m+1)):
				for x in range(n-m+1):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if P[dy][dx] > -1 and S[y+dy][x+dx] - P[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(P,x,y,ans)
						break
				if flag == 0: break
			P = [[P[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print "NA" if ans == [n+1,n+1] else " ".join(map(str,ans))
	except:
		pass

Submission status: Accepted

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == 0:
        break
    W = [list(map(int, input().split())) for i in range(N)]
    P = [list(map(int, input().split())) for i in range(M)]
    P0 = [[0]*M for i in range(M)]

    ans = []
    for t in range(4):
        P1 = []
        for i in range(M):
            for j in range(M):
                if P[i][j] == -1:
                    continue
                P1.append((i, j, P[i][j]))
        for y in range(N-M+1):
            for x in range(N-M+1):
                for i, j, p in P1:
                    if W[y+i][x+j] != p:
                        break
                else:
                    i, j, p = P1[0]
                    ans.append((y+i+1, x+j+1))
                    break
            else:
                continue
            break
        for i in range(M):
            for j in range(M):
                P0[M-1-j][i] = P[i][j]
        P0, P = P, P0
    if ans:
        y, x = min(ans)
        print(x, y)
    else:
        print("NA")

Submission status: Accepted

Solution code:
from itertools import product


def rotate(a):
    return [[a[y][x] for y in range(len(a)-1, -1, -1)] for x in range(len(a))]


while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    picture = [list(map(int, input().split())) for _ in [0]*n]
    piece = [list(map(int, input().split())) for _ in [0]*m]
    ans = []

    for i in range(4):
        for y, x in product(range(m), repeat=2):
            if piece[y][x] != -1:
                dx, dy = x+1, y+1
                break

        for (from_y, to_y), (from_x, to_x) in product(zip(range(n), range(m, n+1)), repeat=2):
            for j, y in zip(range(m), range(from_y, to_y)):
                if not all(v1 == -1 or v1 == v2 for v1, v2 in zip(piece[j], picture[y][from_x:to_x])):
                    break
            else:
                ans.append((from_y+dy, from_x+dx))

        piece = rotate(piece)

    ans.sort()
    print(" ".join(map(str, ans[0][::-1])) if ans else "NA")

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import product
# from line_profiler import LineProfiler

def rotate_clockwise(matrix):
    return list(map(list, zip(*matrix)))[::-1]

def main():
    while(True):
        n,m = map(int, stdin.readline().split())
        if not n:
            break
        w = [list(map(int, stdin.readline().split())) for _ in range(n)]
        p = [list(map(int, stdin.readline().split())) for _ in range(m)]
        rp = [p]
        for _ in range(3):
            p = rotate_clockwise(p)
            rp.append(p)
        ds = [[ [i,j,rp[r][i][j]] for i,j in product(range(m),range(m)) if rp[r][i][j] != -1] for r in range(4)]
        flag = True
        for i,j,a in product(range(n-m+1),range(n-m+1),ds):
            for b in a:
                if w[i+b[0]][j+b[1]] - b[2]:
                    break
            else:
                print(j+a[0][1]+1,i+a[0][0]+1)
                flag = False
                break
        if flag: print("NA")

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Runtime Error

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	scene = [map(int,raw_input().split()) for i in range(n)]
	pic = [map(int,raw_input().split()) for i in range(m)]
	ans = "NA"
	for rot in range(4):
		for y in range(n-m):
			for x in range(n-m):
				flag = 0
				for dy in range(m):
					for dx in range(m):
						if pic[dy][dx] > -1 and scene[y+dy][x+dx] - pic[dy][dx] != 0:
							flag = 1
							break
					if flag == 1: break
				if flag == 0:
					flag1 = 0
					for dy in range(m):
						for dx in range(m):
							if pic[dy][dx] > -1:
								ans = str(x+dx+1)+" "+str(y+dy+1)
								flag1 = 1
								break
						if flag1 == 1: break
			if flag == 0: break
		if flag == 0: break
		pic = [[pic[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
	print ans

Submission status: Runtime Error

Solution code:
def getxy(pic):
	flag = 0
	for dy in range(m):
		for dx in range(m):
			if pic[dy][dx] > -1:
				ans = str(x+dx+1)+" "+str(y+dy+1)
				flag = 1
				break
		if flag == 1: break
	return ans
	
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	scene = [map(int,raw_input().split()) for i in range(n)]
	pic = [map(int,raw_input().split()) for i in range(m)]
	ans = "NA"
	for rot in range(4):
		if scene == pic:
			ans = getxy(pic)
		for y in range(n-m):
			for x in range(n-m):
				flag = 0
				for dy in range(m):
					for dx in range(m):
						if pic[dy][dx] > -1 and scene[y+dy][x+dx] - pic[dy][dx] != 0:
							flag = 1
							break
					if flag == 1: break
				if flag == 0:
					ans = getxy(pic)
			if flag == 0: break
		if flag == 0: break
		pic = [[pic[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
	print ans