1977. 河童重工的防空系统

从灵梦口中得知(买到的情报)幻想乡有防空系统(Powered by 河童重工),于是白渃和托尔需要小心地飞行。

为了避免触发防空警报,他们需要计算防空炮的射程来进行规避。

img

有由 mmnn 行的方格组成的防区,记第 ii jj 的方格坐标是 (i,j)(i,j)​,行从下往上,列从左往右。方格的内容 ai,ja_{i,j} 可能如下:

  1. ai,j=1a_{i,j}=1,代表空地。
  2. ai,j=2a_{i,j}=2,代表障碍物。
  3. ai,j=3a_{i,j}=3,代表炮塔。炮塔有且仅有一个。

定义两点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2) 的曼哈顿距离是 x1x2+y1y2|x_1-x_2|+|y_1-y_2|。炮塔的能够攻击的方格(射程)为所有与自己所在位置的曼哈顿距离小于等于 33 的方格。自身所在方格和超出 mmnn 行的坐标不在射程内。特别地,设炮塔所在方格 (x,y)(x,y),若在射程内有障碍物,则炮塔的攻击会受到遮挡。具体而言:

  • 位于 (x,y+1)(x,y+1) 的障碍物会阻挡 (x1,y+1),(x,y+1),(x+1,y+1),(x1,y+2),(x,y+2),(x+1,y+2),(x,y+3)(x-1,y+1),(x,y+1),(x+1,y+1),(x-1,y+2),(x,y+2),(x+1,y+2),(x,y+3) 七格。
  • 位于 (x,y1)(x,y-1) 的障碍物会阻挡 (x1,y1),(x,y1),(x+1,y1),(x1,y2),(x,y2),(x+1,y2),(x,y3)(x-1,y-1),(x,y-1),(x+1,y-1),(x-1,y-2),(x,y-2),(x+1,y-2),(x,y-3) 七格。
  • 位于 (x+1,y)(x+1,y) 的障碍物会阻挡 (x+1,y1),(x+1,y),(x+1,y+1),(x+2,y1),(x+2,y),(x+2,y+1),(x+3,y)(x+1,y-1),(x+1,y),(x+1,y+1),(x+2,y-1),(x+2,y),(x+2,y+1),(x+3,y) 七格。
  • 位于 (x1,y)(x-1,y) 的障碍物会阻挡 (x1,y1),(x1,y),(x1,y+1),(x2,y1),(x2,y),(x2,y+1),(x3,y)(x-1,y-1),(x-1,y),(x-1,y+1),(x-2,y-1),(x-2,y),(x-2,y+1),(x-3,y) 七格。
  • 位于 (x,y+2)(x,y+2) 的障碍物会阻挡 (x,y+2),(x,y+3)(x,y+2),(x,y+3) 两格。
  • 位于 (x,y2)(x,y-2) 的障碍物会阻挡 (x,y2),(x,y3)(x,y-2),(x,y-3) 两格。
  • 位于 (x+2,y)(x+2,y) 的障碍物会阻挡 (x+2,y),(x+3,y)(x+2,y),(x+3,y) 两格。
  • 位于 (x2,y)(x-2,y) 的障碍物会阻挡 (x2,y),(x3,y)(x-2,y),(x-3,y) 两格。
  • 其他位于射程之内的障碍物只会阻挡障碍物所在本格。

给定方格的内容,请你求出炮塔的可攻击方格有多少格。

输入

输入一行两个整数 n,m(1m,n20)n,m(1\le m,n\le 20)

接下来输入 nn 行,每行 mm 个整数,第 jj 行第 ii 个整数代表 ai,j(1ai,j3)a_{i,j}(1\le a_{i,j}\le 3)。保证有且仅有一个坐标满足 ai,j=3a_{i,j}=3

输出

输出一行一个整数,代表可攻击方格数。

样例

标准输入 复制文本
5 6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 3 1 1
1 1 1 1 1 1
标准输出 复制文本
19
标准输入 复制文本
9 9
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 2 1 1 1 1
1 1 1 1 3 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
标准输出 复制文本
17
标准输入 复制文本
7 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 2 1 1 1 1
1 1 1 3 1 2 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
标准输出 复制文本
21

提示

对样例一,如图所示:

对样例二,如图所示:

对样例三,如图所示:

来源

2023 SCNUCPC 重现赛

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 41
通过 21