I was trying to solve the following 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.
example:
N=3,K=1
P T P
T T P
T P T
Answer:3
I tried a simple BFS solution but my code if failing in which there are alternative P and T,am not able to handle this case with BFS.
My solution:solution(Its a bit lengthy,so didn't paste it here.)
It would be really helpful and highly appreciating if someone could suggest some algorithm or pseudo code for this problem statement.
PS:This was the question of this test.It was a timed test, couldn't solve it.
Thanks.