In this HackerEarth Policemen and thieves problem solution You are given a grid of size N x N that has the following specifications:
  1. Each cell in the grid contains either a policeman or a thief.
  2. A policeman can only catch a thief if both of them are in the same row.
  3. Each policeman can only catch one thief.
  4. A policeman cannot catch a thief who is more than K units away from the policeman.
Write a program to find the maximum number of thieves that can be caught in the grid.


HackerEarth Policemen and thieves problem solution


HackerEarth Policemen and thieves problem solution.

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define MAX 5123
#define NIL 0
#define INF (1<<28)
using namespace std;

char a[51][51];
int police[51][51];
int thief[51][51];

vector< int > G[MAX];
int n, m, match[MAX], dist[MAX];

bool bfs() {
int i, u, v, len;
queue< int > Q;
for(i=1; i<=n; i++) {
if(match[i]==NIL) {
dist[i] = 0;
Q.push(i);
}
else dist[i] = INF;
}
dist[NIL] = INF;
while(!Q.empty()) {
u = Q.front(); Q.pop();
if(u!=NIL) {
len = G[u].size();
for(i=0; i<len; i++) {
v = G[u][i];
if(dist[match[v]]==INF) {
dist[match[v]] = dist[u] + 1;
Q.push(match[v]);
}
}
}
}
return (dist[NIL]!=INF);
}

bool dfs(int u) {
int i, v, len;
if(u!=NIL) {
len = G[u].size();
for(i=0; i<len; i++) {
v = G[u][i];
if(dist[match[v]]==dist[u]+1) {
if(dfs(match[v])) {
match[v] = u;
match[u] = v;
return true;
}
}
}
dist[u] = INF;
return false;
}
return true;
}

int hopcroft_karp() {
int matching = 0, i;
while(bfs())
for(i=1; i<=n; i++)
if(match[i]==NIL && dfs(i))
matching++;
return matching;
}

void solve() {
for(int i=0;i<MAX;i++) G[i].clear();
memset(match,0,sizeof(match));
memset(dist,0,sizeof(dist));

int N, K;
cin>>N>>K;
assert(N>=1 && N<=50);
assert(K>=1 && K<=N);
int cnt_p = 0, cnt_t = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
cin>>a[i][j];
assert(a[i][j]=='P' || a[i][j]=='T');
}
}

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(a[i][j] == 'P') {
cnt_p++;
police[i][j] = cnt_p;
}
else {
cnt_t++;
thief[i][j] = cnt_t;
}

n = cnt_p, m = cnt_t;
int pol,thf;

for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(a[i][j]=='P') {
pol=police[i][j];
for(int k=0;k<N;k++) {
if(abs(k-j) <= K && a[i][k] == 'T' && k!=j) {
thf=thief[i][k];
G[pol].pb(cnt_p + thf);
}
}
}
}
}

int ans = hopcroft_karp();
cout << ans << "\n";
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;cin>>t;
assert(t>=1 && t<=10);
while(t--) solve();
}

Second solution

#include <bits/stdc++.h>

using namespace std;

#define V vector

typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;

typedef V<int> vi;
typedef V<string> vs;
typedef V<LL> vll;
typedef V<double> vd;
typedef V<pii> vpii;

#define forup(i,a,b) for(int i=(a); i<(b); ++i)
#define fordn(i,a,b) for(int i=(a); i>(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define fov(i,a) rep(i,(a).size())
#define foreach(i,X) for(__typeof((X).begin()) i = (X).begin(); i != (X).end(); i++)

#define gi(x) scanf("%d",&x)
#define gl(x) cin >> x
#define gd(x) scanf("%lf",&x)
#define gs(x) cin >> x

#define pn printf("\n")
#define pi(x) printf("%d",x)
#define ppii(x) printf("%d %d ", x.fs, x.sc);
#define ppiin(x) ppii(x); pn;
#define pin(x) printf("%d\n",x)
#define pl(x) printf("%I64d",x)
#define pln(x) cout << x
#define ps(s) cout << s;
#define psn(s) cout << s << "\n"
#define spc printf(" ")
#define prec(x) cout<<fixed<<setprecision(x)

#define all(x) (x).begin(), (x).end()

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

#define fr freopen("input.in", "r", stdin)
#define fw freopen("output.txt", "w", stdout)

#define SET(a, v) memset(a, v, sizeof a)

const int inf = numeric_limits<int>::max();
const LL linf = numeric_limits<LL>::max();
const double EPS = 1e-7;

const int maxn = 5005;
const int logmaxn = log2(maxn) + 3;
const int mod = (int)1e9 + 7;

int Abs(int X) {
if (X >= 0) return X;
return -X;
}

int main() {
// fr;

int T;
char ch;
gi(T);
while (T--) {
int N, K, res = 0;
vi chor, police;
gi(N); gi(K);
rep(i, N) {
chor.clear();
police.clear();
rep(j, N) {
cin >> ch;
assert(ch == 'P' || ch == 'T');
if (ch == 'P') police.pb(j);
else chor.pb(j);
}
int l = 0, r = 0;
while (l < chor.size() && r < police.size()) {
if (Abs(chor[l] - police[r]) <= K) {
++res; ++l; ++r;
} else if (chor[l] < police[r]) ++l;
else ++r;
}
}
pin(res);
}
return 0;
}