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.
@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 …
Can anyone help me to solve this problem I am facing??
Before you solve my query please know that I was not solving the complete question, I was only solving subtask 1 for 30 points.
I get runtime error (SIGSEV) when i submit this code. I think it is because of when I access array values out of valid range. The code runs fine on my machine but rightfully gives error on codechef. Do you have any elegant solution to avoid this problem?
Just because of some invalid corner values I am getting a futile error, I don’t want to write some if conditional statements to solve this problem. It will then get too messy. Please help me!!!
#include<bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main()
{
int t;
cin >> t;
while(t--){
int n,m,k;
cin >> n >> m >> k;
int arr[n+1][m+1];
int x[k] = {0};
int y[k] = {0};
memset(arr, 0, sizeof arr);
for(int i=0; i<k; i++){
int a,b;
cin >> a >> b;
x[i] = a;
y[i] = b;
arr[a][b] = 1;
}
/*for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout << arr[i][j] << " ";
}
cout << endl;
}*/
long long int ans = 0;
for(int i=0; i<k; i++){
for(int j = 0; j < 4; j++) {
int nx = x[i] + dx[j];
int ny = y[i] + dy[j];
if(arr[nx][ny] != 1){
ans++;
}
}
}
cout << ans << endl;
}
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
BOOST();
test(t){
long long n,m,k;cin>>n>>m>>k;
vector<pair<long long ,long long > > plants;
map<pair<long long ,long long >,bool>hash1; // true if contsins plants else false
ll total=0;
for(long long i=0;i<k;i++){
long long r,c;
cin>>r>>c;
plants.push_back(make_pair(r,c));
if(r==1 || r==n)total++; // boundry case
if(c==1 || c==m)total++; // boundry case
hash1[{r,c}]=true;// true if contains plants
}
for(long long i=0;i<k;i++){
long long r=plants[i].ff,c=plants[i].ss;
for(long long j=0;j<4;j++){
long long x=r+dx[j];
long long y=c+dy[j];
if(x<1 || x>n || y<1 || y>m )continue; // boundry case already considered
if(!hash1[{x,y}])total++;
}
}
cout<<total<<endl;
}
}
you may think of them are direction unit vectors. take an pair of corresponding (dx,dy), you will get unit vectors in (+x axis, -x axis, +y axis, -y axis)
