计算可以捕获的最大盗贼数量 [英] Count maximum number of thieves that can be caught

问题描述

问题是这样的：

有一个 N * N 网格。

1. 网格的每个单元格可以具有由P表示的警察或由T表示的小偷。


2. 只有在同一行中，警察才能抓到一个小偷。


3. 警察只能抓一个小偷。


4. 警察不能抓住距离他 K个单位以上的小偷。

1. Each cell of the grid can have either a police denoted by P or a thief denoted by T.
2. A police can catch a thief only if they are in a same row.
3. A police can catch only one thief.
4. A police cannot catch a thief who is more than K units away from it.

计算可捕获的最大盗贼数。

Count maximum number of thieves that can be caught.

TPT

PTP

TTP

T P T
P T P
T T P

输出：3

我使用的方法是，警察需要在给定范围（即k）内，抓住距离他最远的小偷。我已经使用2个队列实施了这种方法，一个队列用于警察，另一个队列用于小偷。

The approach I have used is, a police needs to catch the thief farthest available from him in the given range i.e k. I have implemented this approach using 2 queues, one for policemen and other for thieves.

在24个测试用例中，有18个通过了，其余的答案都是错误的。

如果方法错误，我想知道正确的答案。

如果缺少一些测试用例，我想知道。

Out of 24 test-cases 18 got passed, rest got wrong answer.
If the approach is wrong I would like to know the correct answer.
And if some test case I am missing I would like to know that.

下面您可以找到我的代码段：

Below you can find my code snippet:

import java.util.*;
public class policemenAndThief
{
    public int maxThiefCaught(char[][] mat,int k)
    {
        int count = 0;
        ArrayDeque<Integer> police = null;
        ArrayDeque<Integer> thief = null;
        int n = mat.length;
        for(int i = 0 ; i < n ; i++)
        {
            police = new ArrayDeque<>(n);
            thief = new ArrayDeque<>(n);
            for(int j = 0 ; j < n ; j++)
            {
                if(mat[i][j] == 'T')
                {
                    while(police.isEmpty() == false && j - police.peekFirst() > k)
                    {
                        police.pollFirst();
                    }

                    if(police.isEmpty())
                    {
                        thief.addLast(j);
                    }

                    else
                    {
                        police.pollFirst();
                        count++;
                    }
                }

                else
                {
                    while(thief.isEmpty() == false && j - thief.peekFirst() > k)
                    {
                        thief.pollFirst();
                    }

                    if(thief.isEmpty())
                    {
                        police.addLast(j);
                    }

                    else
                    {
                        thief.pollFirst();
                        count++;
                    }

                }
            }
        }
        return count;
    }
}

推荐答案

C ++解决方案：

int solution (vector<vector<char> > A, int K) {
    int res=0;
   for(int i=0;i<A.size();i++)
   {
       vector<int> pol;
       vector<int> thi;
       for(int j=0;j<A[0].size();j++)
       {
           if (A[i][j] == 'P') 
            pol.push_back(j); 
        else if (A[i][j] == 'T') 
            thi.push_back(j);
       }

       // track lowest current indices of 
    // thief: thi[l], police: pol[r] 

       int l = 0, r = 0; 
    while (l < thi.size() && r < pol.size()) {
        if (abs(thi[l] - pol[r]) <= K) { 
            res++; 
            l++; 
            r++; 
        } 
        // increment the minimum index 
        else if (thi[l] < pol[r]) 
            l++;
        else
            r++; 
    }
    pol.clear();
    thi.clear();
   }
   return res;
}

它可以通过所有24个测试用例。

It passes all 24 test cases.

这篇关于计算可以捕获的最大盗贼数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！