ABC 018 C - 菱形カウント

• 問題
• AC

長方形領域の周りがxで囲われているものとして考える:

xxxxxxx
xxoooox
xooooxx
xooooox
xoxxoox
xxxxxxx

xからの最短距離が$K$以上であるマスがわかれば、その数が答えである。具体的には、マスxを$0$に、マスoを$\inf$に初期化した上で、$0$に初期化した点をすべてキューに入れてBFSすれば良い:

0   0   0   0   0   0   0
0   0   inf inf inf inf 0
0   inf inf inf inf 0   0
0   inf inf inf inf inf 0
0   inf 0   0   inf inf 0
0   0   0   0   0   0   0

↓

0   0   0   0   0   0   0
0   0   1   1   1   1   0
0   1   2   2   1   0   0
0   1   1   1   2   1   0
0   1   0   0   1   1   0
0   0   0   0   0   0   0

計算量は${\mathcal O}(RC)$。