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.