Jump to content
Sign in to follow this  
xtrm0

Nuvem de Cinzas

Recommended Posts

xtrm0

Boa Noite,

Estava a resolver o problema Nuvem de Cinzas, usando só força bruta, e parece que resultou para 70% dos casos.

O que eu fiz, foi calcular a menor distancia de manhattam entre cada nuvem e aeroporto, e depois usando a menor e a maior das distancias calculadas escrever a resposta.

Alguma ideia de como tornar o código mais rápido, ou tenho mesmo de faze-lo por bfs? Se sim, como é que se faz :wallbash:?

Código:

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#define MiN(a, b)  (a < b) ? a : b
#define MaX(a, b)  (a > b) ? a : b
using namespace std;
struct nuvem{
int x,y;
};
struct aeroporto{
   int x, y;
   int min;
};

int main(){
   int L, C;
   vector <nuvem> nv;
   vector <aeroporto> ae;
   char linha[1001];
   nuvem noje; //nuvem usada só para o input
   aeroporto aeoje;  //aeroporto usado só para o input
   aeoje.min = 10000000;
   int aeroportos=0;
   int nuvens=0;
   int minimo=10000000;
   int maximo=0;

   cin >> L >> C;
   for (int x=1; x<=L; x++) {
       scanf ("%s",linha);
       for (int y=1; y<=C; y++) {
           if (linha[y-1]=='#') {
               noje.x=x;
               noje.y=y;
               nv.push_back(noje);
               nuvens++;
           } else if (linha[y-1]=='A') {
               aeoje.x = x;
               aeoje.y = y;
               ae.push_back(aeoje);
               aeroportos++;
           }
       }
   }

   for (int it=0; it<nuvens; it++) {
       for (int nt=0; nt<aeroportos; nt++) {
           ae[nt].min=MiN((abs((nv[it].x-ae[nt].x))+abs((nv[it].y-ae[nt].y))), ae[nt].min);
       }
   }
   for (int nt=0; nt<aeroportos; nt++) {
       minimo=MiN(ae[nt].min, minimo);
       maximo=MaX(ae[nt].min, maximo);
   }

   cout << minimo << " " << maximo << endl;
   return 0;
}

Cumprimentos, Xtrm0


<Signature goes here>

Share this post


Link to post
Share on other sites
xtrm0

Ok. Obrigado, eu já o tinha feito assim, só que esquecime de apagar os aeroportos  😳.

E usando bruteforce, não dava para melhorar?


<Signature goes here>

Share this post


Link to post
Share on other sites
Warrior

O que queres dizer com "usando brute force"? BFS pode-se enquadrar perfeitamente nessa categoria, brute force não é um método por si.

Share this post


Link to post
Share on other sites
xtrm0

Com brute force, quero dizer o codigo que postei (calcular sempre a distancia entre cada nuvem e todos os aeroportos).


<Signature goes here>

Share this post


Link to post
Share on other sites
skiller10

Boas,

Tentei dois tipos de soluções neste problema.

Na primeira maneira tive run time error(30):

    -Consistia em ver o numero de aeroportos no inicio, e depois ir aumentando as nuvens numa matriz e ver quando desaparece o primeiro aeroporto e o ultimo.

Na segunda solução fiz como o xtrmo acho, e tive novamente run time error(20)

    - Consistia em guardar em estruturas todos os aeroportos e nuvens, e ver as distancias minimas e maximas das nuvens aos aeroportos.

Alguém tem uma dica para melhorar?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Warrior

Corrigir os runtime errors?

Faz debug do teu programa com casos que sabes que falham, se necessário recorrendo a ferramentas de debugging.

Share this post


Link to post
Share on other sites
skiller10

Já testei vários casos e deu-me correcto em todos.

Qual das duas maneiras que falei é mais eficiente? a segunda?

Ferramentas de debugging? podes-me dizer nomes de algumas, nunca usei :S

Deixo aqui o codigo também:

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;

//Estrutura para guardar cada aeroporto:****************************************
struct aero{
    int x, y;
    int dist;       
};

//Estrutura para guardar cada nuvem:********************************************
struct nuvem{
    int x, y;   
};

//Calcular a distancia entre o aeroporto e a nuvem:*****************************
int calcDist(int xn, int yn, int xa, int ya){
        float aux, a, b;
        int dist;
    a = (xn-xa)*(xn-xa);
    b = (yn-ya)*(yn-ya);    
    aux = a+b;
    aux = sqrt(aux);
    dist = (int)ceilf(aux);
    return dist;    
};
//******************************************************************************

int main()
{
    int linhas, colunas; //Variaveis para guardar as dimensoes do mapa;
    int nuvens=0, aeros=0; //Contadores para o numero de nuvens e aeroportos;
    int nmin=9999, nmax=0; //Variaveis para guardar os dias das primeiras e ultimas ocorrencias;
    int aux;

//Ler dimensoes do mapa:********************************************************
cin >> linhas >> colunas;
//******************************************************************************

    char mapa[linhas][colunas]; //Matriz para guardar o mapa;

//Ler o mapa e ver quantos aeroportos e nuvens existem:*************************
for(int i=0; i<linhas; i++){
    for(int j=0; j<colunas; j++){
         cin >> mapa[i][j]; 
         if(mapa[i][j]=='#'){
             nuvens ++;
         }
         if(mapa[i][j]=='A'){
             aeros ++;
         }
    }      
}
//****************************************************************************** 

    aero proteg[aeros]; //Estrutura para guardar os aeroportos;
    nuvem infect[nuvens]; //Estrutura para guardar as nuvens;

//Guardar coordenadas das nuvens e aeroportos:**********************************
for(int i=0, k1=0, k2=0; i<linhas; i++){
    for(int j=0; j<colunas; j++){
         if(mapa[i][j]=='A'){
              proteg[k1].x = i;
              proteg[k1].y = j; 
              proteg[k1++].dist = 9999;                
         }
         if(mapa[i][j]=='#'){
              infect[k2].x = i;
              infect[k2++].y = j;                 
         }
    }         
}
//Calcular as distancias entre cada aeroporto e cada nuvem:*********************
for(int i=0; i<nuvens; i++){ 
    for(int j=0; j<aeros; j++){ 
        aux = calcDist(infect[i].x, infect[i].y, proteg[j].x, proteg[j].y);
        if(aux<proteg[j].dist) proteg[j].dist = aux;
    }
}
//Ver qual a distancia minima e a distancia maxima:*****************************
for(int i=0; i<aeros; i++){
    if(proteg[i].dist<nmin) nmin = proteg[i].dist;
    if(proteg[i].dist>nmax) nmax = proteg[i].dist;            
}
//Imprimir resultados:**********************************************************
cout << nmin << " " << nmax << endl;

//system("PAUSE");
return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Não olhei mt para o código mas isto


    char mapa[linhas][colunas]; //Matriz para guardar o mapa;
//... 
    aero proteg[aeros]; //Estrutura para guardar os aeroportos;
    nuvem infect[nuvens]; //Estrutura para guardar as nuvens;

salta logo à vista. Não faças isso. Muito menos dentro de uma função. Provavelmente estás a exceder a memória da stack.

Declara sempre as estruturas de dados grandes como variáveis globais.

PS: mesmo que seja este o problema que leva aos RE, deves ter outros, porque isto só aconteceria nos casos de teste maiores e se tivesses tudo certo, terias pelo menos 50 pontos.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Parece que era mesmo esse o problema, só que agora tenho Time Limit Exceed(70).

Estou a pensar numa maneira de poupar tempo nos calculos, se alguém tiver ideias  ;)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

@skiller10, tiveste TLE, porque não dá para se fazer o problema calculando a manhattan distance. Tens de usar bread first search.

Lê o tópico que o warrior mandou e sê tiveres duvidas, aqui fica o código que eu enviei.

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
struct nuvem{
    int x,y;
};
nuvem noje;
bool visitados[2000][2000];
bool aeroportos[2000][2000];
int aeroportoS=0;
int mintempo=0;
void bfs(int dia, vector <nuvem> nv, int nuv) {
    vector <nuvem> diase;
    int nn=0;
    for (int i=0; i<nuv; i++) {
        if (aeroportos[nv[i].x][nv[i].y]==true) {
            if (mintempo==0) {
                cout << dia << " ";
                mintempo= 1242094823;
            }
            aeroportoS--;
        }

        noje.x=nv[i].x+1;
        noje.y=nv[i].y;
        if (noje.x > 0 && noje.y > 0 && noje.x < 1001 && noje.y < 1001) {
            if (visitados[noje.x][noje.y]==false){
                diase.push_back(noje);
                nn++;
                visitados[noje.x][noje.y]=true;
            }
        }
        noje.x=nv[i].x-1;
        noje.y=nv[i].y;
        if (noje.x > 0 && noje.y > 0 && noje.x < 1001 && noje.y < 1001) {
            if (visitados[noje.x][noje.y]==false){
                diase.push_back(noje);
                nn++;
                visitados[noje.x][noje.y]=true;
            }
        }
        noje.x=nv[i].x;
        noje.y=nv[i].y+1;
        if (noje.x > 0 && noje.y > 0 && noje.x < 1001 && noje.y < 1001) {
            if (visitados[noje.x][noje.y]==false){
                diase.push_back(noje);
                nn++;
                visitados[noje.x][noje.y]=true;
            }
        }
        noje.x=nv[i].x;
        noje.y=nv[i].y-1;
        if (noje.x > 0 && noje.y > 0 && noje.x < 1001 && noje.y < 1001) {
            if (visitados[noje.x][noje.y]==false){
                diase.push_back(noje);
                nn++;
                visitados[noje.x][noje.y]=true;
            }
        }
    }
    if (aeroportoS==0) {cout << dia << endl; return;}
    bfs(dia+1, diase, nn);
    return;
}

int main() {
    int L,C;
    cin >> L >> C;
    int nuvens=0;
    char linha[2000];
    vector <nuvem> nv;
    for (int x=1; x<=L; x++) {
        scanf ("%s",linha);
        for (int y=1; y<=C; y++) {
            if (linha[y-1]=='#') {
                noje.x=x;
                noje.y=y;
                nv.push_back(noje);
                nuvens++;
            } else if (linha[y-1]=='A') {
                aeroportos[x][y]=true;
                aeroportoS++;
            }
        }
    }
    bfs(0,nv,nuvens);
    return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
skiller10

Obrigado, vou estudar agora o bread first search :D


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

Sim, mas eu queria saber se dava para fazer usando a manhattan distance (não dá). E porque achava que bfs era outro algoritmo mais complicado, do que aquele que mostras-te.

Achei que como era usado outro algoritmo mais valia abrir outro tópico.


<Signature goes here>

Share this post


Link to post
Share on other sites
skiller10

O bfs é semelhante ao algoritmo que eu tinha feito de início, só que este é feito recursivamente, e muda a forma como os dados são guardados.

Há algum truque para avaliar um problema, saber se devemos ou não fazer por bruteforce, ou fazer e depois adaptar, todas as dicas são bem vindas :D


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

BFS não é recursivo, é iterativo - usa uma fila - http://www.cppreference.com/wiki/container/queue/start

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

O código do xtrm tá recursivo (embora seja practicamente iterativo porque a recursão é feita no fim da função), mas sem necessidade.

Há algum truque para avaliar um problema, saber se devemos ou não fazer por bruteforce

Praticar problemas até adquirires essa "sensibilidade" para determinar o tipo de um problema. Depende da tua definição de bruteforce, mas normalmente um "bruteforce" dará algo tipo 30~50 pontos, nunca os 100.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Localhost

A minha solução para este problema está-me a dar TLE (5 pontos) e aqui no meu pc ele passa em 0,4s em worst case.. Antes dava-me MLE e agora passou a este TLE estranho. Acho que tem mesmo algo a ver com a memória que estou a usar.. provavelmente devido ao tamanho da queue.. Alguém me pode dar uma ajuda?

#include <cstdio>
#include <queue>

using namespace std;

typedef struct
{
        int x, y, age;
} Cloud;

int L, C, nAirports, nAttacked;
char map[1001][1001];
queue <Cloud> clouds;

void input ()
{
        char state;
        Cloud new_cloud;

        scanf ("%d %d", &L, &C);
        for (int l = 0; l < L; l++)
                for (int c = 0; c < C; c++)
                {
                        scanf ("%c", &state);
                        if (state == '#')
                        {
                                new_cloud.x = l;
                                new_cloud.y = c;
                                new_cloud.age = 0;

                                clouds.push (new_cloud);
                        }
                        else if (state == 'A')
                        {
                                map[l][c] = 'A';
                                nAirports = 1 + nAirports;
                        }
                }

        nAttacked = nAirports;
}

void add_cloud (int x, int y, int age)
{
        Cloud new_cloud;

        new_cloud.x = x;
        new_cloud.y = y;
        new_cloud.age = age;

        clouds.push (new_cloud);

        if (map[new_cloud.x][new_cloud.y] != 'A')
                map[new_cloud.x][new_cloud.y] = '#';
}

int main ()
{
        int size = 0, days = 0;
        Cloud dequeue_cloud;

        input ();
        while (nAttacked > -1)
        {
                ++days;
                size = clouds.size ();

                for (int k = 0; k < size; k++)
                {
                        dequeue_cloud = clouds.front ();
                        clouds.pop ();

                        if (map[dequeue_cloud.x][dequeue_cloud.y] == 'A')
                        {
                                nAttacked = nAttacked - 1;
                                if (nAirports - 1 == nAttacked)
                                        printf ("%d ", dequeue_cloud.age);
                        }

                        if (dequeue_cloud.x < L && map[dequeue_cloud.x + 1][dequeue_cloud.y] != '#')
                                add_cloud (dequeue_cloud.x + 1, dequeue_cloud.y, dequeue_cloud.age + 1);

                        if (dequeue_cloud.y < C && map[dequeue_cloud.x][dequeue_cloud.y + 1] != '#')
                                add_cloud (dequeue_cloud.x, dequeue_cloud.y + 1, dequeue_cloud.age + 1);

                        if (dequeue_cloud.x > 0 && map[dequeue_cloud.x - 1][dequeue_cloud.y] != '#')
                                add_cloud (dequeue_cloud.x - 1, dequeue_cloud.y, dequeue_cloud.age + 1);

                        if (dequeue_cloud.y > 0 && map[dequeue_cloud.x][dequeue_cloud.y - 1] != '#')
                                add_cloud (dequeue_cloud.x, dequeue_cloud.y - 1, dequeue_cloud.age + 1);
                }
        }
        printf ("%d\n", days);

        return 0;
}

// @ End of file!


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Estás a processar várias vezes as mesmas nuvens.

Na minha opiniao devias usar dois queue, um para o dia actual, e um para o dia seguinte, e ir sempre trocando-os. Em vez de usares cloud.age.


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Exacto. Percebi isso há pouco. Estou a repetir várias vezes a mesma nuvem, o que obviamente vai resultar em MLE.


here since 2009

Share this post


Link to post
Share on other sites
mogers

Nem compilei o código, não tenho mt tempo agora, e vi o código apenas por alto mas aqui vão alguns reparos (posso tar enganado por ter visto à pressa):

- o input e construção da queue parece-me correcto

- devias juntar os 4 ifs para adicionar clouds num só. as condições dos ifs são compativeis x entre 0..C-1, y entre 0..L-1, etc. colocas o check dentro do add_cloud

Por fim, penso que não processas varias vezes a mesma nuvem, mas tenho quase a certeza que o seguinte mapa te provoca um ciclo infinito:

A..
A.#

edit: estava errado, o problema é que tu estás a fazer mapa[x ][y] no add_queue em vez de y,x. O mesmo nos ifs


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.