Problem:


E : 台風 / Typhoon

問題文

南北方向に H ，東西方向に W の大きさの町がある． 町には一辺の長さが 1 の正方形の区画に隙間なく整備されており，全ての区画に 1 軒ずつ家が建っている．

この町のある区画の上空で台風が発生し，被害を与えた後，ある区画の上空で温帯低気圧に変化した． 変化した後は被害を与えない． 下図のように，台風は高さ 3, 幅 3 の正方形であり， ★のついたマスを中心と呼ぶことにする．台風は 8 近傍に区画単位で移動する． つまり，台風の中心は辺または頂点を共有する区画(現在の区画を含む)に移るように，全体を伴って移動する． ただし，町の外に台風がはみ出ることはなく，

台風の中心は，下の図の網掛けのように，北から 0 番目と H &minus; 1 番目，西から 0 番目と W &minus; 1 番目の区間は通らないように移動する．

家は台風が一度上空に来ると，以下のように被害の程度が変化する．

損壊ナシ → 一部損壊 → 半壊 → 全壊 → 跡形ナシ

だが，幸い跡形ナシとなった家は無かったようだ． 各家の被害の状況が与えられるので，台風が発生した地点と，温帯低気圧に変化した地点を求めよ． ただし，発生した区画を北から s_i 番目，西から s_j 番目， 温帯低気圧に変化した区画を北から t_i 番目，西から t_j 番目とすると， 2 つの地点は 10000 t_i + t_j ≤ 10000 s_i + s_j を満たすように定まる．

入力

H \ W
D_{11} \ … \ D_{1W}
D_{21} \ … \ D_{2W}
…
D_{H1} \ … \ D_{HW}

D_{ij} は北から i 番目， 西から j 番目の家の被害の程度を以下のように表す整数である．

0 : 損壊ナシ

1 : 一部損壊

2 : 半壊

3 : 全壊

制約

整数である

入力は答えが一意に定まるようなもののみ与えられる

3 ≤ H,W ≤ 500

0 ≤ D_{ij} ≤ 3

出力

答えを以下のように 1 行で出力せよ．

s_i \ s_j \ t_i \ t_j

サンプル

サンプル入力1

7 5
0 0 0 0 0
0 1 1 1 0
0 2 2 2 0
0 3 3 3 0
0 2 2 2 0
0 1 1 1 0
0 0 0 0 0

サンプル出力1

4 2 2 2

サンプル入力2

6 6
0 0 0 1 1 1
0 0 0 2 2 2
0 0 1 3 3 2
1 2 3 3 2 1
1 2 3 2 1 0
1 2 2 1 0 0

サンプル出力2

4 1 1 4

サンプル入力3

4 4
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0

サンプル出力3

1 1 1 1

 

Sample input:
7 5
0 0 0 0 0
0 1 1 1 0
0 2 2 2 0
0 3 3 3 0
0 2 2 2 0
0 1 1 1 0
0 0 0 0 0


Sample output:
4 2 2 2

Submission status: Wrong Answer

Solution code:
import copy
H,W = map(int, input().split())
f = [list(map(int, input().split())) for i in range(H)]
path = []
s = []
t = []
b_flag = False
r_flag = False

def search(f, path):
	y, x = path.pop()
	for i in range(-1, 2):
		for j in range(-1, 2):
			f[y+i][x+j] -= 1
			if f[y+i][x+j] == -1:
				return
	
	for l in f:
		if (l.count(0) != W):
			break
	else:
		print(str(y)+" "+str(x))
		exit()

	for i in range(4):
		ny = y+[0, -1, -1, 0][i]
		nx = x+[0, 0, 1, 1][i]
		if (ny > 0 and nx < W-1 and f[ny][nx] != 0):
			path += [[ny, nx]]
			search(copy.deepcopy(f), path)
		else:
			return


for y in range(H-1, -1, -1):
	for x in range(W):
		if (f[y][x] != 0):
			path += [[y-1, x+1]]
			b_flag = True
			break
	if (b_flag):
		break

s = map(str, path[0])
print(" ".join(s), end=" ")
search(f, path)