Uma empresa de construção civil especializada em reparos precisa de software de simulação de alagamento de imóveis.
Para evitar custos adicionais, a empresa disponibiliza sensores que identifica se determinada parte do imóvel está alagada.
O alagamento passar para a póxima parte alagável (horizontalmente e verticalmente) uma vêz por minuto, porém o alagamento não é capaz de vencer a parede.
O valor do reparo é calculado por quantos minutos cada parte do imóvel se manteve alagada até que o alagamento alcance no mínimo DOIS sensores. (o sensor só dispara depois que foi alagado por pelo menos um minuto)
Modelo de entrada
3 4
2 2 1 5
0 0 1 0
2 0 0 0
Os dois primeiros números são as dimenções da matriz.
Valores possívels na matriz:
0 - Parte alagável (pode alagar)
1 - Parede (não pode alagar)
2 - Sensores (pode alagar)
5 - Fonte do alagamento
A saida é a soma de quantos minutos todo o imóvel se manteve alagado até que o alagamento alcance no mínimo DOIS sensores.
Exemplo
Entrada:
2 3
2 0 5
0 2 0
Saida:
9
Explicando: o resultado final a matriz de MINUTOS final seria
1 2 3
0 1 2
Logo a soma da 9 segundos.
Lembrando que o ideial é fazer um programa que rode o mais rápido possível (complexidade).
Postem as soluções e algumas novas entradas e saídas para ver se todo mundo está com o mesmo resultado.
Temos que:
#include <bits ⁄ stdc ++. h>
usando namespace std;
⁄ * Nó da lista de links * ⁄
struct Node {
dados int;
struct Node * next;
};
⁄ * Dada uma referência (ponteiro para ponteiro) para
o chefe de uma lista e um int, empurre um novo
nó na frente da lista. * ⁄
void push (struct Node ** head_ref, int new_data)
{
struct Node * new_node = novo Nó;
new_node-> data = new_data;
new_node-> next = (* head_ref);
(* head_ref) = new_node;
}
⁄⁄ Função para reverter a lista vinculada
Nó * reverseList (Node * head)
{
⁄⁄ Stack para armazenar elementos da lista
empilhar <Nó *> stk;
⁄⁄ Empurre os elementos da lista para empilhar
Nó * ptr = cabeça;
while (ptr-> next! = NULL) {
stk.push (ptr);
ptr = ptr-> next;
}
⁄⁄ Pop da pilha e substitua
⁄⁄ valor dos nós atuais ´
cabeça = ptr;
while (! stk.empty ()) {
ptr-> next = stk.top ();
ptr = ptr-> next;
stk.pop ();
}
ptr-> next = NULL;
cabeça de retorno;
}
⁄⁄ Função para imprimir a lista vinculada
void printList (Node * head)
{
while (head) {
cout << head-> data << "";
cabeça = cabeça-> próxima;
}
}
⁄⁄ Driver Code
int main ()
{
⁄ * Comece com a lista vazia * ⁄
struct Node * head = NULL;
⁄ * Use push () para construir a lista abaixo
1-> 2-> 3-> 4-> 5 * ⁄
empurrar (e cabeça, 5);
empurrar (e cabeça, 4);
empurrar (e cabeça, 3);
empurrar (e cabeça, 2);
empurrar (e cabeça, 1);
head = reverseList (cabeça);
printList (cabeça);
return 0;
}
Temos que:
#include <bits / stdc ++. h>
usando namespace std;
/ * Nó da lista de links * /
struct Node {
dados int;
struct Node * next;
};
/ * Dada uma referência (ponteiro para ponteiro) para
o chefe de uma lista e um int, empurre um novo
nó na frente da lista. * /
void push (struct Node ** head_ref, int new_data)
{
struct Node * new_node = novo Nó;
new_node-> data = new_data;
new_node-> next = (* head_ref);
(* head_ref) = new_node;
}
// Função para reverter a lista vinculada
Nó * reverseList (Node * head)
{
// Stack para armazenar elementos da lista
empilhar <Nó *> stk;
// Empurre os elementos da lista para empilhar
Nó * ptr = cabeça;
while (ptr-> next! = NULL) {
stk.push (ptr);
ptr = ptr-> next;
}
// Pop da pilha e substitua
// valor dos nós atuais '
cabeça = ptr;
while (! stk.empty ()) {
ptr-> next = stk.top ();
ptr = ptr-> next;
stk.pop ();
}
ptr-> next = NULL;
cabeça de retorno;
}
// Função para imprimir a lista vinculada
void printList (Node * head)
{
while (head) {
cout << head-> data << "";
cabeça = cabeça-> próxima;
}
}
// Driver Code
int main ()
{
/ * Comece com a lista vazia * /
struct Node * head = NULL;
/ * Use push () para construir a lista abaixo
1-> 2-> 3-> 4-> 5 * /
empurrar (e cabeça, 5);
empurrar (e cabeça, 4);
empurrar (e cabeça, 3);
empurrar (e cabeça, 2);
empurrar (e cabeça, 1);
head = reverseList (cabeça);
printList (cabeça);
return 0;
}
Para escrever sua resposta aqui, entre ou crie uma conta.
Compartilhar