Policemen and thieves
Tag(s):

## Algorithms, Searching, Two pointer

Problem
Editorial
Analytics

You are given a grid of size $N \times 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 \le T \le 10$
$1 \le N \le 1000$
$1 \le K \le N*N$

SAMPLE INPUT
1
3 1
P T P
T P T
T T P

SAMPLE OUTPUT
3

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

National Instruments Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting