Policemen and thieves

You are given a grid of size N×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.

Example:

Input: n = 3, k = 1, board = {{'P', 'T', 'P'}, {'T', 'P', 'T'}, {'T', 'T', 'P'}}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

bool check(vector<vector<char>> &board,
           int x, int y, int k, int n)
{
    for (int i = 1; i <= k; i++)
    {

        if (y - i >= 0 && board[x][y - i] == 'T')
        {
            board[x][y - i] = '0';
            return true;
        }
    }
    for (int i = 1; i <= k; i++)
    {
        if (i + y < n && board[x][i + y] == 'T')
        {
            board[x][i + y] = '0';
            return true;
        }
    }
    return false;
}

void policemanAndThief(int n, int k, vector<vector<char>> &board)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        vector<int> police;
        vector<int> theif;
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 'P')
            {
                police.push_back(j);
            }
            else
            {
                theif.push_back(j);
            }
        }
        int l = 0;
        int r = 0;
        while (l < police.size() && r < theif.size())
        {
            if (abs(police[l] - theif[r]) <= k)
            {
                ans++;
                l++;
                r++;
                continue;
            }
            if (police[l] > theif[r])
            {
                r++;
            }
            else
            {
                l++;
            }
        }
    }
    cout << ans << "\n";
}
int main()
{

    int n = 3, k = 1;

    vector<vector<char>> board = {{'P', 'T', 'P'},
                                  {'T', 'P', 'T'},
                                  {'T', 'T', 'P'}};

    policemanAndThief(n, k, board);

    return 0;
}