# HELP IN MARLA

PROBLEM
This problem comes under graph theory. I didn’t get any approach to it using graphs (the editorial said to use DFS but I didn’t understand how to). That’s why I used a different method.

``````#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector <pair <int, int>> h(0);
while (n--)
{
vector <int> s(m);
for (int i = 0; i < m; ++i) cin >> s[i];
int prev = 0, size = 0;
for (int i = 0; i < m; ++i)
{
if (prev == 0)
{
size = 1;
prev = s[i];
} else {
if (s[i] == prev) ++size;
else {
h.push_back(make_pair(s[i], size));
size = 1;
}
}
if (i == m-1)
{
h.push_back(make_pair(s[i], size));
size = 1;
}
}
}
int max = -1, bank = 0;
sort(h.begin(), h.end());
for (auto i : h)
{
if (i.second > max)
{
max = i.second;
bank = i.first;
}
}
cout << bank << " " << max << '\n';
}
``````

I go through all values in a line and store their count (i.e., if they are consecutive) in a vector of pairs. I do this for all n lines in a single vector (because I need the maximum number of banks I can hack from all given values). I sort the vector according to the bank type so that I only have to check if the current max value is greater than the second value of a pair and I need to make that the current max.

This approach works fine for a few cases but I fail to understand why I get a WA verdict for the others.

This is the verdict:

You can’t just do every row independently. For example

``````3 2 1
3 4 1
2 3 1
``````

You would print

``````1 1
``````

``````1 3
``````
1 Like

Thanks

I used BFS instead of DFS, pushing the adjacent unexplored cells in queue till it’s empty. I’m getting WA for 2 test cases 1 in each subtask. What am I doing wrong?

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m; cin>>n>>m;
int grid[n][m];
int vis[n][m];
memset(vis,0,sizeof(vis));
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++)
cin>>grid[i][j];
}
int count=0,s=1e9+1;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (vis[i][j]==0) {
queue<pair<int,int>> Q;
Q.push({i,j});
int c=0;
while (!Q.empty()) {
auto x=Q.front();
int a=x.first,b=x.second;
c++;Q.pop();
vis[a][b]=1;
int type=grid[a][b];
if (a!=0 && type==grid[a-1][b] && vis[a-1][b]==0)
Q.push({a-1,b});
if (a!=n-1 && type==grid[a+1][b] && vis[a+1][b]==0)
Q.push({a+1,b});
if (b!=0 && type==grid[a][b-1] && vis[a][b-1]==0)
Q.push({a,b-1});
if (b!=m-1 && type==grid[a][b+1] && vis[a][b+1]==0)
Q.push({a,b+1});
}
if (count<c)
count=c,s=grid[i][j];
else if (count==c) {
if (grid[i][j]<s)
s=grid[i][j];
}
else {}
}
}
}
cout<<s<<" "<<count<<"\n";
return 0;
}
``````

Your BFS implementation is wrong. You should set `vis` to 1 as soon as you push it in the queue.

1 Like

Thank you soo much, that did it!