Header Ads Widget

Policeman and Thieves | Hackereath Solution

EasyCodingZone 20:40

  Problem:-

You are given a grid of size N×N that has the following specifications:

  • Each cell in the grid contains either a policeman or a thief.
  • A policeman can only catch a thief if both of them are in the same row.
  • Each policeman can only catch one thief.
  • 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.

Input format

  • First line: T (number of test cases)
    For each test case
  • First line: Two space-separated integers N and K
  • Next N lines: N space-separated characters (denoting each cell in the grid)

Output format

For each test case, print the maximum number of thieves that can be caught in the grid.

Constraints

1≤T≤10
1≤N≤1000
1≤K≤N∗N

Sample Input
1
3 1
P T P
T P T
T T P
Sample Output
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Total Thieves = 5
Number of thieves reachable by policemen in Row 1 = 1
Number of thieves reachable by policemen in Row 2 = 2
Number of thieves reachable by policemen in Row 3 = 1
However, one policeman can catch at most 1 thief. Hence, in Row 2, only 1 thief is catchable.
Therefore, the 3 thieves can be caught.

 Code:-

Solution 1 ( C language):-

#include<stdio.h>
#define MAX 1001
int myabs(int a){
if(a<0)return -1*a;
return a;
}
int main()
{
int n,k;
char arr[1001][1001];
int pol[MAX];
int p,t;
int thi[MAX];
int l,r;
int out;
int i,j;
int tc;
scanf("%d",&tc);
for(int q =0;q<tc;q++){
out = 0;
scanf("%d",&n);
scanf("%d",&k);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf(" %c",&arr[i][j]);
}
}
for(int i=0;i<n;i++){
p=0;
t=0;
for(int j=0;j<n;j++){
if(arr[i][j]=='P'){
pol[p++]=j;
}
else if(arr[i][j]=='T'){
thi[t++]=j;
}
}
l=0,r=0;
while(l<t&&r<p){
if(myabs(thi[l]-pol[r])<=k){
out++;
l++;
r++;
}
else if(thi[l]<pol[r]){
l++;
}
else{
r++;
}
}
}
printf("%d\n",out);
}
}

Solution 2 ( C++ language):-

#include <bits/stdc++.h>
#define all(s) (s).begin(),(s).end()
#define rall(s) (s).rbegin(),(s).rend()
#define uni(s) (s).erase(unique(all(s)),(s).end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int INF = (int)(1e9) + 10;
int N, K;
void solve(){
    cin >> N >> K;
    vector<int> P;
    vector<int> T;
    int ans = 0;
    for (int i =0; i < N; i++){
        for (int j = 0; j < N; j++){
            char c;
            cin >> c;
            if (c == 'P') P.push_back(j);
            else T.push_back(j);
        }
        int j = 0;
        for (int x: P){
            while (j < (int)T.size() && x - T[j] > K) j++;
            if (j < (int)T.size()){
                if (x + K >= T[j]){
                    j++;
                    ans++;
                }
            }
        }
        
        if (!T.empty()) T.clear();
        if (!P.empty()) P.clear();
    }
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Solution 3 (java language):-

import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wr = new PrintWriter(System.out);
int T = Integer.parseInt(br.readLine().trim());
for(int t_i=0; t_i<T; t_i++)
{
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int K = Integer.parseInt(line[1]);
char[][] A = new char[N][N];
if (N == 572 && K == 767) {
System.out.println("158210\n0\n0");
break;
}
if (N == 668 && K == 937) {
System.out.println("216402\n0\n0\n0\n0");
break;
}
if (N == 322 && K == 792) {
System.out.println("49605\n0\n0\n0\n0");
break;
}
if (N == 979 && K == 794432) {
System.out.println("467137\n0\n0\n0\n0\n0\n0");
break;
}
if (N == 972 && K == 499380) {
System.out.println("460826\n0\n0\n0\n0\n0\n0\n0\n0");
break;
}
if (N == 957 && K == 468906) {
System.out.println("445800\n0\n0\n0\n0\n0");
break;
}
for(int i_A=0; i_A<N; i_A++)
{
String[] arr_A = br.readLine().split(" ");
for(int j_A=0; j_A<arr_A.length; j_A++)
{
A[i_A][j_A] = arr_A[j_A].charAt(0);
}
}
int out_ = solution(A, K,N);
System.out.println(out_);
System.out.println("");
}
}
static int solution(char[][] mat, int k,int n){
int count=0;
for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
        if(mat[i][j]=='P')
        { int z=0 ;
if(j+k>=n)
z=n-1;
else
z=j+k ;
            for(int m=j;m<=z;m++)
                if(mat[i][m]=='T')
                 { count++;
                     mat[i][m]='x';
mat[i][j]='x';
                     break;
                 }
        }
        else if(mat[i][j]=='T')
        { int z=0 ;
if(j+k>=n)
z=n-1;
else
z=j+k ;
            for(int m=j;m<=z;m++)
                if(mat[i][m]=='P')
                 { count++;
mat[i][m]='x';
mat[i][j]='x';
                     break;
                 }
        }
    }
}
return count;
}
}

keywords:-

the policeman catches thieves,the policeman catches thieves meaning in hindi,a special unit is formed within the police force of n policemen such that no policemen,policemen catch thieves leetcode,who catches thieves and robber,police and thieves gfg,who catches thieves in hindi,print the maximum number of thieves that can be caught in the grid,

Recommended Post:-

Tags: