A maior rede de estudos do Brasil

Mario adora convidar seus amigos para brincar em sua casa. Então decidiu convidar seus amigos para brincarem de Polícia e Ladrão. O jogo consiste em

Mario adora convidar seus amigos para brincar em sua casa. Então decidiu convidar seus amigos para brincarem de Polícia e Ladrão. O jogo consiste em dois grupos, um grupo é a polícia e o outro é o grupo dos ladrões. Os ladrões devem se esconder e a polícia deve capturá-los. Caso a polícia consiga capturá-los e prendê-los os ladrões perdem o jogo e caso a polícia não consiga capturá-los os ladrões vencem o jogo. Mario decidiu que seria do grupo da polícia e que teria que procurar seus amigos do grupo dos ladrões e capturá-los, porém, algum de seus amigos sentiram-se em desvantagens por não possuírem lugares estratégicos para se esconder no seu quintal. Portanto decidiram planejar uma forma em que poderiam deixar os policiais sem saída e terem chances de ganhar o jogo. Para isso montaram um labirinto usando caixas de papelão e marcaram como “0” todos os lugares no quintal aonde os policiais poderiam atravessar e como “1” aonde os policiais não poderiam atravessar. Os ladrões irão se esconder sempre no último espaço do labirinto, Se os policiais ficarem encurralados no labirinto os ladrões vencem e poderão comemorar a fuga, mas se os policiais alcançarem o ultimo espaço do labirinto os policiais serão os vencedores. Os policiais poderão andar somente nos blocos marcados como 0. Sua tarefa é determinar a partir do labirinto quem vai ganhar o jogo. Entrada A primeira entrada consiste de um inteiro T(1 ≤ T ≤ 400) indicando o número de casos de testes. As próximas T entradas consistem de uma matriz 5x5, composta de valores inteiros, sendo 0 ou 1. Saída Seu programa deverá imprimir COPS caso o grupo dos policiais ganhem, e ROBBERS caso o grupo dos ladrões ganhem.


2 resposta(s) - Contém resposta de Especialista

User badge image

RD Resoluções Verified user icon

Há mais de um mês

O algoritmo será:

{

// Retorne com o máximo de ladrões

// that can be caught.

int policeThief(char arr[], int n, int k)

{

int res = 0;

ArrayList thi = new ArrayList();

ArrayList pol = new ArrayList();

// store indices in the ArrayList

for (int i = 0; i < n; i++) {

if (arr[i] == 'P')

pol.add(i);

else if (arr[i] == 'T')

thi.add(i);

}

// track lowest current indices of

// thief: thi[l], police: pol[r]

int l = 0, r = 0;

while (l < thi.size() && r < pol.size()) {

// can be caught

if (Math.abs(thi.get(l) - pol.get(r)) <= k) {

res++;

l++;

r++;

}

// increment the minimum index

else if (thi.get(l) < pol.get(r))

l++;

else

r++;

}

return res;

}

// Driver program

public static void main(String args[])

{

int k, n;

char arr1[] =new char[] { 'P', 'T', 'T',

'P', 'T' };

k = 2;

n = arr1.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr1, n, k));

char arr2[] =new char[] { 'T', 'T', 'P', 'P',

'T', 'P' };

k = 2;

n = arr2.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr2, n, k));

char arr3[] = new char[]{ 'P', 'T', 'P', 'T',

'T', 'P' };

k = 3;

n = arr3.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr3, n, k));

}

}

O algoritmo será:

{

// Retorne com o máximo de ladrões

// that can be caught.

int policeThief(char arr[], int n, int k)

{

int res = 0;

ArrayList thi = new ArrayList();

ArrayList pol = new ArrayList();

// store indices in the ArrayList

for (int i = 0; i < n; i++) {

if (arr[i] == 'P')

pol.add(i);

else if (arr[i] == 'T')

thi.add(i);

}

// track lowest current indices of

// thief: thi[l], police: pol[r]

int l = 0, r = 0;

while (l < thi.size() && r < pol.size()) {

// can be caught

if (Math.abs(thi.get(l) - pol.get(r)) <= k) {

res++;

l++;

r++;

}

// increment the minimum index

else if (thi.get(l) < pol.get(r))

l++;

else

r++;

}

return res;

}

// Driver program

public static void main(String args[])

{

int k, n;

char arr1[] =new char[] { 'P', 'T', 'T',

'P', 'T' };

k = 2;

n = arr1.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr1, n, k));

char arr2[] =new char[] { 'T', 'T', 'P', 'P',

'T', 'P' };

k = 2;

n = arr2.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr2, n, k));

char arr3[] = new char[]{ 'P', 'T', 'P', 'T',

'T', 'P' };

k = 3;

n = arr3.length;

System.out.println("Maximum thieves caught: "

+policeThief(arr3, n, k));

}

}

Essa pergunta já foi respondida por um dos nossos especialistas