HackerEarth Policemen and thieves problem solution

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.

#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;
}