FENCE - Editorial

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:

\{(x+1,y),(x,y+1),(x-1,y),(x,y-1)\}

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.

2 Likes

Thank you. That explanation helped. Gave a new logic.

Can you please explain the values of dx and dy arrays

@anu788
Here dx and dy is used for checking wether a plant is present in the nearby spots.
In particular dx : It is used here for checking if plant is present above or below the spot(x,y).
like wise dy : It is used here for checking if plant is present to the left of the spot or right.
hope it helps
happy coding …

2 Likes

I did this with map but got partial Correct(70 point) and Wrong answer for the 30 point.
Here is the code.

Anyone check this!!