Hello Everyone.
So i was going trying this problem on codeforces
and used the following code
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define IOS std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0)
using namespace std;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<pii> vii;
ll ans=0;
ll black=0;
unordered_set<int> cycle_path;
void dfs(vvc& gr,vvi& clr, int u, int v, int p, vvi& vstd, vvi& fb, vvi& tn, vii& pth)
{
//if(vstd[u][v]) return;
//cout << "p = " << p << " u=" <<u << " v=" << v << endl;
int i=u,j=v;
vstd[u][v]=p;
pth.pb(mp(u,v));
tn[u][v]+=1;
if(clr[u][v]==0)
{
fb[u][v]+=1;
}
if(gr[u][v]=='R') j=j+1;
if(gr[u][v]=='L') j=j-1;
if(gr[u][v]=='U') i=i-1;
if(gr[u][v]=='D') i=i+1;
if(vstd[i][j]==0)
{
fb[i][j]=fb[u][v];
tn[i][j]=tn[u][v];
dfs(gr,clr,i,j,p,vstd,fb,tn,pth);
}
else if(vstd[i][j]==p)
{
ans += tn[u][v]-tn[i][j]+1;
cycle_path.insert(p);
return;
}
else
{
return;
}
}
void fndMaxBlack(vvi& fb)
{
}
int main(void) {
int T;
cin>>T;
while(T--)
{
int n,m;
char ch;
cin>>n>>m;
vvi grid_clr(n, vector<int>(m));
vvc grid_dir(n, vector<char>(m));
vvi grid_vstd(n, vector<int>(m));
vvi fund_blk(n, vector<int>(m));
vvi ttl_nds(n, vector<int>(m));
vii vpth[m*n];
cycle_path.clear();
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>ch;
grid_clr[i][j]=ch-'0';
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>ch;
grid_dir[i][j]=ch;
}
}
ans=0;
black=0;
int path=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(grid_vstd[i][j]==0)
{
path=path+1;
dfs(grid_dir,grid_clr,i,j,path,grid_vstd,fund_blk,ttl_nds,vpth[path]);
}
}
}
cout << ans << " " << black << endl;
}
return 0;
}
So My approch was to find all the cycle and total no of nodes in all the cycle will be the total robots i can place.
Then I thought that the total no of black cell can be maximized by having total no of all the black cell in all cycle which will be the count for “black”.
But this was the moment i knew i Affd -Up. Because the maximum no of black cell will be maximum of those cells which were on the path which were leading to the cycle including the cycle as well. I mean it might be a dynamic problem or something. So can someone tell me how can I implement the function
.
findMaxBlack()
.
grid_clr => clr of the particualr cell
grid_dir=> direction of movement from particual place
grid_vstd=>If the particular cell is visited or not and also tell if a particular cell is visited then by
which path because i have unique path number for every single cycle
grid.
fnd_black=> total no of blk nodes found till this cell
ttl_nds => total no of nodes till this cell on the path
vpth=> represent the cell forming the path.
Thanks in advance. please help it was hard writhing this whole thing.
@vijju123
@cenation092
@admin