早稲田大学プログラミングコンテスト2019 B - 10 puzzle

場合分けが無限にある。
条件がきつい順に
全部０の場合→０
５が含まれていない場合→ No
全部５以下の場合→１
min(h, w) > 1 なら
最大値 9 → 4
最大値 8 → 3
最大値 6,7 → 2
となり、
そして上記以外で、h or w = 1 のときは、５の左右の列で最大値ごとに計算する必要がある。それを全ての５で計算して最小値をだす。えぐい。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools

h,w = map(int,readline().split())
c = [list(map(int,input().split())) for i in range(h)]
b = list(itertools.chain.from_iterable(c))
a = set(itertools.chain.from_iterable(c))

if a == {0}:
  print('Yes 0')
  exit()
  
if not 5 in a:
  print('No')
  exit()
  
if max(a) == 5:
  print('Yes 1')
  exit()
  
if w == 1 or h == 1:
  g = []
  p = 0
  m = 0
  for i in b:
    if i == 5:
      if m == 9:
        p += 3
      elif m == 8:
        p += 2
      elif m > 5:
        p += 1
      c = {0}
      g.append(p)
      p = 0
    else:
      m = max(i,m)
  if m == 9:
    p += 3
  elif m == 8:
    p += 2
  elif m > 5:
    p += 1
  g.append(p)
  k  = 100
  for i in range(len(g)-1):
    kk = max(g[:i+1])+max(g[i+1:])
    ks = min(ks,kk)
  print('Yes {}'.format(ks+1))
  exit()
  
if 9 in a:
  print('Yes 4')
  exit()
  
if 8 in a:
  print('Yes 3')
  exit()
  
print('Yes 2')