Wrong answer on hidden test cases please help->
#include<bits/stdc++.h>
using namespace std;
int m,n;
int x,y;
vector MAP;
vector<pair<int,int>> points{{0,1},{1,0},{-1,0},{0,-1}};
bool inside(int x,int y)
{
if((x>=0 and x<m) and (y>=0 and y<n))
return true;
return false;
}
auto solution(int i,int j)
{
int count=0;
queue<pair<int,int>> q;
q.push({i,j});
MAP[i][j]=‘0’;
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
count++;
for(pair<int,int> dest:points)
{
int xx=dest.first+p.first;
int yy=dest.second+p.second;
if(inside(xx,yy) and MAP[xx][yy]==‘1’)
{
MAP[xx][yy]=‘0’;
q.push({xx,yy});
}
}
}
return count;
}
bool comp(int a,int b)
{return a>b;}
void solve()
{
cin>>n>>m;
MAP.resize(n);
int res;
vector land;
for(int i=0;i<n;i++)
{
cin>>MAP[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(MAP[i][j]==‘1’)
{
res=solution(i,j);
land.push_back(res);
}
}
}
int sum=0;
sort(land.begin(),land.end(),comp);
for(int i=1;i<land.size();i+=2)
{
sum+=land[i];
}
cout<<sum<<endl;
}
//********************************************** TEST CASES ******************************************
void testcases(int t)
{
while(t–)
{
solve();
}
}
//******************************************** MAIN FUNCTION *****************************************
int main()
{
int t;
cin>>t;
testcases(t);
}
The grid size is n*m hence there can be O(n \cdot m) possible connected components and sorting it would take O(n \cdot m \cdot \log{(n \cdot m)}) time.
Bro try to add recursion limit like
from sys import setrecursionlimit
setrecursionlimit(100000)
it will worked for me
Bro try to add recursion limit like in python
from sys import setrecursionlimit
setrecursionlimit(100000)
it will worked for me
I tried to solve this using recursion and it passed 2/4 testcases. Can anyone say why this code isnt working.
#include<bits/stdc++.h>
using namespace std;
int n,m, cnt;
vector<vector<int>> grid;
int check(int x, int y)
{
if(x>=n || y>=m || grid[x][y]==0) //outside the bound
return 0;
grid[x][y]=0; //removing the already checked island
cnt=1;
return cnt+ check(x,y+1)+ check(x+1, y); //returns the size of the island
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
string str;
grid.resize(n, vector<int> (m));
for(int i=0;i<n;i++)
{
cin>>str;
for(int j=0;j<str.length();j++)
{
if(str[j]=='1')
grid[i][j]=1;
else
grid[i][j]=0;
}
}
vector<int> sizes; //stores the sizes of all islands
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]!=0)
sizes.push_back(check(i,j));
}
}
sort(sizes.begin(), sizes.end(), greater<int>());
int sum=0;
for(int i=0;i<sizes.size();i++)
if(i%2==1)
sum+=sizes[i];
cout<<sum<<endl;
}
return 0;
}
//
// Created by Rohit on 4/29/2021.
//
#include <bits/stdc++.h>
using namespace std;
class Game{
int row[4]={1,-1,0,0};
int col[4]={0,0,1,-1};
int n=0,m=0;
public:
int findLand(vector<vector> grid,int i,int j,vector<vector> &visited){
//base case
if(grid[i][j]=='0')
return 0;
visited[i][j]=true;
int land=1;
for(int k=0;k<4;k++){
int x=i+row[k];
int y=j+col[k];
if(isValid(x,y) && !visited[x][y])
land+=findLand(grid,x,y,visited);
}
return land;
}
bool isValid(int i,int j){
return (i>=0) && (j>=0) && (i<n) && (j<m);
}
int playerGame(vector<vector<char>> &grid){
n=grid.size(),m=grid[0].size();
vector<vector<bool>> visited(n,vector<bool> (m,false));
priority_queue<int> pq;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='1' && !visited[i][j]){
int temp=findLand(grid,i,j,visited);
pq.push(temp);
}
}
}
int p1=0,p2=0;
bool turn =true;
while(!pq.empty()){
if(turn){
p1+=pq.top();
turn=false;
}else{
p2+=pq.top();
turn=true;
}
pq.pop();
}
return p2;
}
};
int main() {
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<vector<char>> grid(n,vector<char> (m,0));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>grid[i][j];
Game g;
cout<<g.playerGame(grid)<<endl;
}
return 0;
}
Can anyone tell me why I am getting tle?
from sys import setrecursionlimit
setrecursionlimit(100000)
T = int(input())
def CheckSide1(x,y):
global COUNT
W[x][y] = 0
if x+1<=N-1 and W[x+1][y]==1:
COUNT+=1
CheckSide1(x+1,y)
if y+1<=M-1 and W[x][y+1]==1:
COUNT+=1
CheckSide1(x,y+1)
if x-1>=0 and W[x-1][y]==1:
COUNT+=1
CheckSide1(x-1,y)
if y-1>=0 and W[x][y-1]==1:
COUNT+=1
CheckSide1(x,y-1)
else:
return
for i in range(T):
COUNT=0
W = []
res = []
N,M = input().split()
N,M = [int(N), int(M)]
for k in range(N):
x = [int(x) for x in str(input())]
W.append(x)
for i in range(N):
for j in range(M):
if W[i][j]==1:
COUNT=1
CheckSide1(i,j)
res.append(COUNT)
COUNT=0
res = sorted(res)
points = [0, 0]
for i in range(0, len(res)):
if(i % 2):
points[1] += res[i]
else :
points[0] += res[i]
print(points[1])
Why I’m getting WA, can anyone explain?
@vichitr could you plz tell me why my code is giving WA in last subtask…
or can you give any tc for which code is giving WA
CodeChef: Practical coding for everyone
1 Like
Mistake:
if(x-1<n && grid[x-1][y]=='1')
{
q.push(make_pair(x-1,y));
grid[x-1][y]='0';
}
if(y-1<m && grid[x][y-1]=='1')
{
q.push(make_pair(x,y-1));
grid[x][y-1]='0';
}
The check x-1<n instead of x-1>=0 and y-1<m instead of y-1>=0.
1 Like
Why is my solution giving rutime error
Pls help
my sol
I am facing a very weird error in which after the function ends instead of coming back to main and running the next test case it give me a runtime error pls help.
#include <bits/stdc++.h>
using namespace std;
int counter, n, m;
void visit(int i, int j, vector<vector<bool>> &vis, string *dfs)
{
if(vis[i][j]==0)
{
vis[i][j]=1;
if(dfs[i][j]=='0')
return;
else if(dfs[i][j]=='1')
{
if(i<n-1)
visit(i+1, j, vis, dfs);
if(j<m-1)
visit(i, j+1, vis, dfs);
counter++;
return;
}
}
}
void solve (){
int i, g, answer;
cin>>n>>m;
string dfs[n];
int arr[(n*m)/2];
for(i=0;i<n;i++)
{
cin>>dfs[i];
}
vector<vector<bool>> vis(n, vector<bool>(m, 0));
for(i=0;i<n; i++)
{
for(int j=0;j<m; j++)
{
counter=0;
visit(i, j, vis, dfs);
arr[g]=counter;
g++;
}
}
sort(arr, arr+g, greater<int>());
for(i=1;i<g;i=i+2)
{
answer=arr[i]+answer;
}
cout<<answer<<endl;
return;
}
int main() {
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> ans;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
ans.push_back(s);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<vector<int>> vis(n, vector<int>(m, 0));
vector<int> groups;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (ans[i][j] == '1' && vis[i][j] == 0)
{
int count = 0;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
auto it = q.front();
q.pop();
count++;
int x = it.first;
int y = it.second;
vis[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int newx = x + dx[k];
int newy = y + dy[k];
if (ans[newx][newy] == '1' && newx<m && newx>=0 && newy<n && newy>=0)
{
q.push({newx, newy});
}
}
}
groups.push_back(count);
}
}
}
sort(groups.begin(),groups.end());
reverse(groups.begin(),groups.end());
}
return 0;
}
bro can u pls tell me why my code is giving tle
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> ans;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
ans.push_back(s);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<vector<int>> vis(n, vector<int>(m, 0));
vector<int> groups;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (ans[i][j] == '1' && vis[i][j] == 0)
{
int count = 0;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
auto it = q.front();
q.pop();
count++;
int x = it.first;
int y = it.second;
vis[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int newx = x + dx[k];
int newy = y + dy[k];
if (ans[newx][newy] == '1' && newx<m && newx>=0 && newy<n && newy>=0)
{
q.push({newx, newy});
}
}
}
groups.push_back(count);
}
}
}
sort(groups.begin(),groups.end());
reverse(groups.begin(),groups.end());
int ts=0;
for(int i=0;i<groups.size();i++)
{
if(i%2==1) ts+=groups[i];
}
cout<<ts<<endl;
}
return 0;
}