Submission #1176890


Source Code Expand

# encoding: utf-8
#入力
temp=input().split()
H=int(temp[0])
W=int(temp[1])
K=int(temp[2])
s=[[int(i) for i in input()]for i in range(H)]

"""
このプログラムでは、まず7~9という大きな数字を核として、それぞれが最大値になるように隣接の最大を結合して拡大していく。
上手く行けば、隣の隣まで計算したうえでの最大値が取れる拡大方法を考える。

注意:実行時間に応じて、核にする数字の下限を変化させること。
手順
まず、大きな数字がどこにあるかをexistHighをTrueにすることで示す。
次に、それぞれに応じて9個になるまで拡大して、獲得できる点数pointに、その組み合わせをplaceとして、placeをpointに、
[点数,[組み合わせ]]の形式でappendする。
後はsortして、逆順にansに組み合わせをappendしていく。
随時その組み合わせの要素がusedにてFalseであることを確認してから、used=Trueにすることで、
被ったときはansに組み込まないようにする。
"""
#点数と場所のデータ
tempAns=[]
#答え
ans=[]
#7~9の存在を考える
existHigh=[[False for i in range(W)] for j in range(H)]
for i in range(H):
	for j in range(W):
		if s[i][j]>6:
			existHigh[i][j]=True

#実行
for i1 in range(H):
	for j1 in range(W):
		#高い数字である かつ 使用していない
		if existHigh[i1][j1]==True:
			#今回のピースで使うマスと点数(i,j)<=(H,W)
			tempPiece=[[i1,j1]]
			tempPoint=s[i1][j1]
			#使用済みか否か
			tempUsed=[[False for i in range(W)] for j in range(H)]
			#使用を宣言
			tempUsed[i1][j1]=True
			#K-1個追加していきます
			for temp0 in range(K-1):
				#隣接しているマスの最大値とその場所
				tempMax=-1
				tempMaxSquare=[-1,-1]
				for tempSquare in tempPiece:
					#前回が2個同時進めの場合
					#上端でない場合
					if 0<tempSquare[0]:
						if s[tempSquare[0]-1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]-1][tempSquare[1]]==False:
							tempMax=s[tempSquare[0]-1][tempSquare[1]]
							tempMaxSquare=[tempSquare[0]-1,tempSquare[1]]
					#下端でない場合
					if tempSquare[0]<H-1:
						if s[tempSquare[0]+1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]+1][tempSquare[1]]==False:
							tempMax=s[tempSquare[0]+1][tempSquare[1]]
							tempMaxSquare=[tempSquare[0]+1,tempSquare[1]]
					#左端でない場合
					if 0<tempSquare[1]:
						if s[tempSquare[0]][tempSquare[1]-1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]-1]==False:
							tempMax=s[tempSquare[0]][tempSquare[1]-1]
							tempMaxSquare=[tempSquare[0],tempSquare[1]-1]
					#右端でない場合
					if tempSquare[1]<W-1:
						if s[tempSquare[0]][tempSquare[1]+1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]+1]==False:
							tempMax=s[tempSquare[0]][tempSquare[1]+1]
							tempMaxSquare=[tempSquare[0],tempSquare[1]+1]
							
				#周囲が0しかない場合
				if tempMax<1:
					break
				#pointとplaceの更新(1つ場所を追加)
				tempUsed[tempMaxSquare[0]][tempMaxSquare[1]]=True
				tempPoint*=s[tempMaxSquare[0]][tempMaxSquare[1]]
				tempPiece.append(tempMaxSquare)
			#データを代入
			else:
				tempAns.append([tempPoint,tempPiece])

#点数順にする(ただし昇順)
tempAns.sort()
#点数の高い方から使っていく。
#もしused=Trueの場所があったらスキップ
#全部Falseなら、ans候補に入れて全部True
used=[[False for i in range(W)] for j in range(H)]
#print(tempAns)
while len(tempAns)>1:
	#print(len(tempAns))
	#print(len(ans))
	data=tempAns.pop()
	piece=data[1]
	for square in piece:
		if used[square[0]][square[1]]:
			break
	else:
		ans.append(piece)
		for square in piece:
			used[square[0]][square[1]]=True
		continue
	#被っていた場合、再度pieceを作ってtempAnsに入れる。
	
	for square in piece:
		if used[square[0]][square[1]]==False and s[square[0]][square[1]]>6:
			tempPiece=[[square[0],square[1]]]
			break
	else:
		continue
	
	#使用済みか否か
	tempUsed=[[False for i in range(W)] for j in range(H)]
	#使用を宣言
	tempUsed[tempPiece[0][0]][tempPiece[0][1]]=True
	tempPoint=s[tempPiece[0][0]][tempPiece[0][1]]
	#K-1個追加していきます
	for temp0 in range(K-1):
		#隣接しているマスの最大値とその場所
		tempMax=-1
		tempMaxSquare=[-1,-1]
		for tempSquare in tempPiece:
			#前回が2個同時進めの場合
			#上端でない場合
			if 0<tempSquare[0]:
				if s[tempSquare[0]-1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]-1][tempSquare[1]]==False and used[tempSquare[0]-1][tempSquare[1]]==False:
					tempMax=s[tempSquare[0]-1][tempSquare[1]]
					tempMaxSquare=[tempSquare[0]-1,tempSquare[1]]
			#下端でない場合
			if tempSquare[0]<H-1:
				if s[tempSquare[0]+1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]+1][tempSquare[1]]==False and used[tempSquare[0]+1][tempSquare[1]]==False:
					tempMax=s[tempSquare[0]+1][tempSquare[1]]
					tempMaxSquare=[tempSquare[0]+1,tempSquare[1]]
			#左端でない場合
			if 0<tempSquare[1]:
				if s[tempSquare[0]][tempSquare[1]-1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]-1]==False and used[tempSquare[0]][tempSquare[1]-1]==False:
					tempMax=s[tempSquare[0]][tempSquare[1]-1]
					tempMaxSquare=[tempSquare[0],tempSquare[1]-1]
			#右端でない場合
			if tempSquare[1]<W-1:
				if s[tempSquare[0]][tempSquare[1]+1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]+1]==False and used[tempSquare[0]][tempSquare[1]+1]==False:
					tempMax=s[tempSquare[0]][tempSquare[1]+1]
					tempMaxSquare=[tempSquare[0],tempSquare[1]+1]
					
		#周囲が0しかない場合
		if tempMax<1:
			break
		#pointとplaceの更新(1つ場所を追加)
		tempUsed[tempMaxSquare[0]][tempMaxSquare[1]]=True
		tempPoint*=s[tempMaxSquare[0]][tempMaxSquare[1]]
		tempPiece.append(tempMaxSquare)
	#データを代入
	else:
		tempAns.append([tempPoint,tempPiece])
		tempAns.sort()
	
	
	
	
	
	
	
			
#RE対策。ちゃんと答えの形式になってるかの確認
#Kマスの塊の数
temp=len(ans)
#使用した場所が被ってないか再度見る
used=[[False for i in range(W)] for j in range(H)]
#失敗時のindex確認
badlist=[]
for i in range(temp):
	#要素がちゃんと8個あるかどうか
	if len(ans[i])!=8:
		badlist.append(i)
		continue
	#場所が被ってないか
	for j in range(K):
		if used[ans[i][j][0]][ans[i][j][1]]==False:
			used[ans[i][j][0]][ans[i][j][1]]=True
		else:
			badlist.append(i)
			break
bad=len(badlist)
#結局いくつ塊が出来たのか
print(temp-bad)
#順番に書いてく
for i in range(temp):
	#失敗時はスキップ
	if not i in badlist:
		for j in range(K):
			sent=str(ans[i][j][0]+1)
			sent+=" "
			sent+=str(ans[i][j][1]+1)
			print(sent)

Submission Info

Submission Time
Task A - Multiple Pieces
User toma25
Language Python (3.4.3)
Score 925329
Code Size 7024 Byte
Status AC
Exec Time 300 ms
Memory 4316 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 93338 / 1343058 87992 / 1343058 95266 / 1343058 87799 / 1343058 99716 / 1343058 89195 / 1343058 95265 / 1343058 85468 / 1343058 96580 / 1343058 94710 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 290 ms 4188 KB
subtask_01_02.txt AC 258 ms 4188 KB
subtask_01_03.txt AC 300 ms 4188 KB
subtask_01_04.txt AC 268 ms 4188 KB
subtask_01_05.txt AC 299 ms 4188 KB
subtask_01_06.txt AC 261 ms 4188 KB
subtask_01_07.txt AC 289 ms 4316 KB
subtask_01_08.txt AC 253 ms 4188 KB
subtask_01_09.txt AC 266 ms 4188 KB
subtask_01_10.txt AC 289 ms 4188 KB