**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Ashish Gupta

**Tester:** Zhong Ziqian

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

SIMPLE

**PREREQUISITES**:

Basic data structures

**PROBLEM**:

You’re given N\times M grid, K cells in this grid contain a plant. You’re going to build a fence between each pair of adjacent cells u and v such that exactly one of these cells contains plant. Also fence must be built on the boundary of the grid if adjacent cell to this boundary contains plant.

**EXPLANATION**:

Let’s keep a two-dimensional map in which for cell (x,y) we will keep 1 if it contains plant and 0 otherwise. When you add a new plant (x,y) you have to check all the adjacent cells:

For each cell which doesn’t contain a plant you have to add 1 to the answer and for each cell which contains a plant you should subtract 1. In first case you have to create a fence to separate our cell from that neighbor and in the second case you have to remove the fence because both adjacent cells are plants now. Possible implementation:

```
int N, M, K;
cin >> N >> M >> K;
map<int, map<int, int>> A;
int ans = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
while(K--) {
int x, y;
cin >> x >> y;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
ans += A[nx][ny] ? -1 : 1;
}
A[x][y] = 1;
}
cout << ans << endl;
```

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.