question : CodeChef: Practical coding for everyone
my submission : CodeChef: Practical coding for everyone
my problem :i have seen the editorial video and tried to write the solution but its giving some error i have tried to find the eerors but could’nt find it
when i tried to run on some more sample test cases i found out that the size of the land area that i am storing inside a vector it showing some wierd value ,there are some testcase which it runs properly like the sample test case given in the question also some of my test cases but the test case taken in the video editorial for it it is showing wrong answer.
my code :
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t–)
{
ll n,m,i,j,chef=0;
cin>>n>>m;
ll mt[n+1][m+1];
char ch;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>ch;
if(ch==‘0’)
mt[i][j]=0;
else
mt[i][j]=1;
}
}
vector land;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(mt[i][j]==1)
{
ll sz=0;
vector<pair<ll,ll> > v;
v.push_back(make_pair(i,j));
sz++;
while(v.size()!=0)
{
pair<ll,ll> p = v.back();
mt[p.first][p.second]=0;
v.pop_back();
if((p.first+1<=n)&&(mt[p.first+1][p.second]==1))
{
v.push_back(make_pair(p.first+1,p.second));
sz++;
}
if((p.first-1>0)&&(mt[p.first-1][p.second]==1))
{
v.push_back(make_pair(p.first-1,p.second));
sz++;
}
if((p.second+1<=m)&&(mt[p.first][p.second+1]==1))
{
v.push_back(make_pair(p.first,p.second+1));
sz++;
}
if((p.second-1>0)&&(mt[p.first][p.second-1]==1))
{
v.push_back(make_pair(p.first,p.second-1));
sz++;
}
}
land.push_back(sz);
}
}
}
sort(land.begin(),land.end());
reverse(land.begin(),land.end());
for(i=1;i<land.size();i+=2)
chef+=land[i];
cout<<chef<<‘\n’;
}
// your code goes here
return 0;
}
Sorry, can you paste your code in proper C++ formatting (markdown) ! The current code isnt even compiling !
1 Like
sry for the inconvenience now i have pasted my submission link at the top you can check it out from there
Mark the cell as visited the moment you push it into the BFS queue. In your current code you mark the cell when you pop it from the queue.
i have done what you have said but it still doesn’t pass you in your video have used queue and in mine i have used vector but logic is completely same can you plzz look at it closely
I have made changes in your code and submitted, I got an AC… have a look
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t--)
{
ll n, m, i, j, chef = 0;
cin >> n >> m;
ll mt[n + 1][m + 1];
char ch;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
cin >> ch;
if (ch == '0')
mt[i][j] = 0;
else
mt[i][j] = 1;
}
}
vector<ll> land;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (mt[i][j] == 1)
{
ll sz = 0;
vector<pair<ll, ll> > v;
v.push_back(make_pair(i, j));
mt[i][j] = 0;
while (v.size() != 0)
{
pair<ll, ll> p = v.back();
// mt[p.first][p.second] = 0;
v.pop_back();
sz++;
if ((p.first + 1 <= n) && (mt[p.first + 1][p.second] == 1)) {
v.push_back(make_pair(p.first + 1, p.second));
auto [xx, yy] = v.back();
mt[xx][yy] = 0;
}
if ((p.first - 1 > 0) && (mt[p.first - 1][p.second] == 1)) {
v.push_back(make_pair(p.first - 1, p.second));
auto [xx, yy] = v.back();
mt[xx][yy] = 0;
}
if ((p.second + 1 <= m) && (mt[p.first][p.second + 1] == 1)) {
v.push_back(make_pair(p.first, p.second + 1));
auto [xx, yy] = v.back();
mt[xx][yy] = 0;
}
if ((p.second - 1 > 0) && (mt[p.first][p.second - 1] == 1)) {
v.push_back(make_pair(p.first, p.second - 1));
auto [xx, yy] = v.back();
mt[xx][yy] = 0;
}
}
land.push_back(sz);
}
}
}
sort(land.begin(), land.end());
reverse(land.begin(), land.end());
for (i = 1; i < land.size(); i += 2)
chef += land[i];
cout << chef << '\n';
}
// your code goes here
return 0;
}
thankyou so much for helping i understood where i was getting wrong when i found a neighbouring cell of land at that time only i should convert it into water this is what i was missing to think