ABC186F Rook on Grid
むずかった・・・ 解説AC
問題
上を見よう
解法
A:→↓でいけるやつ
B:↓→でいけるやつとして
A∨Bが求まればいいので
A∨B=A+B-(A∧B)で求めればいい．
AとBはそれぞれ各列or各行において最小となる成分を事前に計算しておけば良し（ここまではできた）
A∧Bについては，左の列から見ていった時に出てきた障害物より右側はBで行くことができないのでそこの部分を省く
BITにy=0において行けるところまでの高さ分だけ1を加えておいて，上記の考察をもとに障害物が出てきたところでそこの高さの部分の列を差し引いてやればいい感じに求まる
