English · Original
Chinese · Translation
Formal · Original
Theater stage is a rectangular field of size _n_ × _m_. The director gave you the stage's plan which actors will follow. For each cell it is stated in the plan if there would be an actor in this cell or not.
You are to place a spotlight on the stage in some _good_ position. The spotlight will project light in one of the four directions (if you look at the stage from above) — left, right, up or down. Thus, the spotlight's position is a cell it is placed to and a direction it shines.
A position is _good_ if two conditions hold:
* there is no actor in the cell the spotlight is placed to;
* there is at least one actor in the direction the spotlight projects.
Count the number of _good_ positions for placing the spotlight. Two positions of spotlight are considered to be different if the location cells or projection direction differ.
## Input
The first line contains two positive integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 1000) — the number of rows and the number of columns in the plan.
The next _n_ lines contain _m_ integers, 0 or 1 each — the description of the plan. Integer 1, means there will be an actor in the corresponding cell, while 0 means the cell will remain empty. It is guaranteed that there is at least one actor in the plan.
## Output
Print one integer — the number of _good_ positions for placing the spotlight.
[samples]
## Note
In the first example the following positions are _good_:
1. the (1, 1) cell and right direction;
2. the (1, 1) cell and down direction;
3. the (1, 3) cell and left direction;
4. the (1, 3) cell and down direction;
5. the (1, 4) cell and left direction;
6. the (2, 2) cell and left direction;
7. the (2, 2) cell and up direction;
8. the (2, 2) and right direction;
9. the (2, 4) cell and left direction.
Therefore, there are 9 _good_ positions in this example.
剧院舞台是一个大小为 $n × m$ 的矩形区域。导演给了你一份演员的站位计划，其中每个格子标明了该位置是否有演员。
你需要在舞台上放置一盏聚光灯，位置必须是“良好”的。聚光灯会朝四个方向之一（从上方观察舞台）投射光线：左、右、上或下。因此，聚光灯的位置由它所在的格子和投射方向共同决定。
一个位置是“良好”的，当且仅当满足以下两个条件：
请计算可以放置聚光灯的“良好”位置总数。两个聚光灯位置被视为不同，当且仅当它们所在的格子或投射方向不同。
第一行包含两个正整数 $n$ 和 $m$（$1 ≤ n, m ≤ 1000$）——计划的行数和列数。
接下来 $n$ 行，每行包含 $m$ 个整数（每个为 $0$ 或 $1$）——描述计划。整数 $1$ 表示对应格子有演员，$0$ 表示该格子为空。保证计划中至少有一个演员。
请输出一个整数——可以放置聚光灯的“良好”位置数量。
在第一个例子中，以下位置是“良好”的：
因此，本例中有 $9$ 个“良好”位置。
## Input
第一行包含两个正整数 $n$ 和 $m$（$1 ≤ n, m ≤ 1000$）——计划的行数和列数。接下来 $n$ 行，每行包含 $m$ 个整数（每个为 $0$ 或 $1$）——描述计划。整数 $1$ 表示对应格子有演员，$0$ 表示该格子为空。保证计划中至少有一个演员。
## Output
请输出一个整数——可以放置聚光灯的“良好”位置数量。
[samples]
## Note
在第一个例子中，以下位置是“良好”的：格子 (1, 1) 且方向为右；格子 (1, 1) 且方向为下；格子 (1, 3) 且方向为左；格子 (1, 3) 且方向为下；格子 (1, 4) 且方向为左；格子 (2, 2) 且方向为左；格子 (2, 2) 且方向为上；格子 (2, 2) 且方向为右；格子 (2, 4) 且方向为左。因此，本例中有 $9$ 个“良好”位置。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the stage grid.
Let $ G \in \{0,1\}^{n \times m} $ be the grid, where $ G[i][j] = 1 $ if an actor is present at cell $ (i,j) $, else $ 0 $.
Let $ P = \{ (i, j, d) \mid 0 \le i < n,\ 0 \le j < m,\ d \in \{ \text{up}, \text{down}, \text{left}, \text{right} \} \} $ be the set of all possible spotlight positions, where $ (i,j) $ is the spotlight location and $ d $ is the direction of projection.
**Constraints**
1. $ 1 \le n, m \le 1000 $
2. $ \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} G[i][j] \ge 1 $
**Objective**
A position $ (i, j, d) \in P $ is *good* if:
- The spotlight is placed on an **empty** cell: $ G[i][j] = 0 $,
- The light beam in direction $ d $ **does not hit any actor** before exiting the grid.
For each direction $ d $, the beam from $ (i,j) $ travels along a straight line until it leaves the grid. The beam is blocked if it encounters a cell with $ G[x][y] = 1 $ along its path.
Count the number of *good* positions $ (i, j, d) \in P $ satisfying the above conditions.
API Response (JSON)
{
"problem": {
"name": "B. Spotlights",
"description": {
"content": "Theater stage is a rectangular field of size _n_ × _m_. The director gave you the stage's plan which actors will follow. For each cell it is stated in the plan if there would be an actor in this cell ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF729B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Theater stage is a rectangular field of size _n_ × _m_. The director gave you the stage's plan which actors will follow. For each cell it is stated in the plan if there would be an actor in this cell ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "剧院舞台是一个大小为 $n × m$ 的矩形区域。导演给了你一份演员的站位计划，其中每个格子标明了该位置是否有演员。\n\n你需要在舞台上放置一盏聚光灯，位置必须是“良好”的。聚光灯会朝四个方向之一（从上方观察舞台）投射光线：左、右、上或下。因此，聚光灯的位置由它所在的格子和投射方向共同决定。\n\n一个位置是“良好”的，当且仅当满足以下两个条件：\n\n请计算可以放置聚光灯的“良好”位置总数。两个聚光灯位置...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the stage grid. \nLet $ G \\in \\{0,1\\}^{n \\times m} $ be the grid, where $ G[i][j] = 1 $ if an actor is present at cell $ (i,j) ...",
"is_translate": false,
"language": "Formal"
}
]
}