2020第11回ブルーブリッジカップ大会ソフトウェア類国試合C/C++大学B組B題題解

皆さんの解法を見てみると、暴力的なbfsで解くことが多いことがわかりました.ここでは数学で巧みに取る方法を紹介し、皆さんの考えを広げてみましょう.
テーマ説明B:拡散
青ちゃんは無限大の特殊なキャンバスに絵を描いた.このキャンバスは1つの格子図と見なすことができ、各格子は1つの2次元の整数座標で表すことができる.ブルーちゃんはキャンバスでまずいくつかのポイントを注文しました:(0,0)、(2020,11)、(11,14)、(2000,2000).このいくつかの格子に黒があるだけで、他の位置は白いです.1分ごとに黒が少し広がります.具体的には、1つの格子の中が黒であれば、上、下、左、右の4つの隣接する格子に拡散し、この4つの格子も黒(元が黒であれば黒)になります.すみません、2020分後、キャンバスに黒い格子がいくつありますか.
構想
逆思考では、この平面内の任意の点を考えています.もしこの点が2020歩以内にこの4つの点の任意の点に着くことができたら、その点は黒いはずです.それでは、問題は既知の2点座標に転化して、この2点の距離を求めます.この距離は実はマンハッタンの距離です.興味のある人は検索して見ることができます.ここで式を直接与えて、d(i,j)=|X 1-X 2|+|Y 1-Y 2|とするとxとyの上下限の確定しか残っておらず、Xの下限は横座標の最小値から2020を減らし、Xの上限は横座標の最大値に2020を加え、Yの上下限は同じである.
コード#コード#
複雑度は高いですが、空欄を埋めると上手に取れます...

#include
#include

using namespace std;

int main()
{
     
	int xy[][2]={
      {
     0,0 }, {
     2020, 11}, {
     11, 14}, {
     2000, 2000} };
    int ans = 0;
	for( int i=-2020; i<=4040; ++i )
		for( int j=-2020; j<=4020; ++j )
			for( int k=0; k<4; ++k )
				if( abs( i-xy[k][0] ) + abs( j-xy[k][1] ) <= 2020 )
				{
     
					++ans;
					break;
				}
	printf("%d
", ans );
	return 0;
}  // 20312088