1

Estou querendo resolver um problema de programação. O enunciado está aqui:

http://olimpiada.ic.unicamp.br/pratique/programacao/nivel1/2014f1p1_setas

Fiz um código, mas na hora de enviar dá problema em algumas entradas. Fala que deu T: tempo limite excedido.

Gostaria de melhorar ele, porém sem mudar a lógica. Será que teria como?

Segue o código abaixo:

#include <stdio.h>

char matriz[502][502];
int n, contador, contadorx, contadory, resultado;

int AnalisaBordas(){
    //Essa funcao analisa as bordas e atribui X na matriz se elas indicarem que sai do tabuleiro
    for (contador=1;contador<n+1;contador++){
        //Analisa a primeira linha
        if(matriz[1][contador] == 'A')
            matriz[1][contador] = 'X';

        //Analisa a ultima linha
        if(matriz[n][contador] == 'V')
            matriz[n][contador] = 'X';

        //Analisa a primeira coluna
        if(matriz[contador][1] == '<')
            matriz[contador][1] = 'X';

        //Analisa a ultima coluno
        if(matriz[contador][n] == '>')
            matriz[contador][n] = 'X';
    }
    return 0;
}

int AnalisaVizinhos(int i, int j){
    //Essa funcao analisa os vizinhos da matriz [i][j]

    //Analisa a matriz a direita
    if(matriz[i][j+1] == '<')
        matriz[i][j+1] = 'X';

    //Analisa a matriz a matriz a esquerda
    if(matriz[i][j-1] == '>' )
        matriz[i][j-1] = 'X';

    //Analisa a matriz abaixo
    if(matriz[i+1][j] == 'A')
        matriz[i+1][j] = 'X';

    //Analisa a matriz acima
    if(matriz[i-1][j] == 'V')
        matriz[i-1][j] = 'X';
    return 0;
}

int main(){ 
    resultado = 0;
    scanf("%d",&n);


    //loop para adicionar os caracteres
    for (contador=1;contador<=n;contador=contador+1){
        for (contadorx=0;contadorx<=n;contadorx=contadorx+1)
            matriz[contador][contadorx] = getchar();    

    }

    AnalisaBordas(); 

    //loop para executar a funcao que analisa vizinhos 
    //executada n*n vezes para trata todos os casos possiveis
    for (contadory=1;contadory<=(n*n);contadory++)
        for (contador=1;contador<=n;contador=contador+1)
            for (contadorx=1;contadorx<=n;contadorx=contadorx+1)
                if(matriz[contador][contadorx] == 'X')
                    AnalisaVizinhos(contador,contadorx);


    //loop para contar quantas posicoes sao inseguras
    for (contador=1;contador<=n;contador=contador+1)
        for (contadorx=1;contadorx<=n;contadorx=contadorx+1)
            if(matriz[contador][contadorx] == 'X')
                resultado += 1;

    printf("%d\n",(n*n - resultado));//exibe quantas posicoes sao seguras
    return 0;
}
5
  • Por que suas funções retornam int se o valor não é usado pra nada? Commented 3/11/2016 às 17:31
  • Mas será q é isso q tá influenciando ?
    – Abism
    Commented 3/11/2016 às 18:00
  • 1
    Provavelmente não, foi só uma observação. Tá mais com cara de que o problema é esse seu loop triplo. Commented 3/11/2016 às 18:41
  • Pois é no pior dos casos o primeiro o for fica com 500*500 aí é muito para percorrer, pois ele analisa e se achar um X ele chama a função para analisar os vizinhos o que tá demorando...por isso eu gostaria de saber se dá para melhorar para fazer isso em menos tempo ou alguma coisa parecida
    – Abism
    Commented 3/11/2016 às 19:05
  • Isso tá com cara de que fica melhor com programação dinâmica, já que sempre que um quadrado for considerado não-seguro, todos os que apontam para ele também são não-seguros, então o resultado dele pode ser reaproveitado. Commented 3/11/2016 às 19:15

1 Resposta 1

1

Dá para fazer várias melhorias. Vamos começar pelas mais simples:

  1. Evite usar variavel = variavel + 1. É mais simples e menos propenso a erros usar variavel++.

  2. Evite usar variáveis globais, pois são consideradas uma má prática de programação por vários motivos. Utilize parâmetros de funções. No exemplo abaixo eu só deixei a matriz como global, porque colocar ela como parâmetro deixaria as coisas bem mais complicadas, embora seja perfeitamente possível mesmo assim.

  3. Não declare o retorno como int se o valor retornado não for utilizado para nada. Utilize void nesse caso.

  4. Lembre-se que em C, a primeira posição é a posição 0, e não a posição 1. No seu algoritmo você está alocando, porém não está utilizando a posição 0.

  5. Utilize as chaves nos laços for e nos ifs. Para entender o porquê, veja o trecho dessa minha outra resposta que tem o título "Chaves após if, else, while e for".

  6. É possível colocar algumas das tarefas que estão dentro do seu main em funções especializadas, a fim de melhor organizar o código.

O seu algoritmo tem 3 fors aninhados um dentro do outro. O externo percorre n^2 células (onde n é o tamanho do quadrado), enquanto que cada um dos laços internos também percorre n vezes (um para a altura e outro para a largura). Assim sendo, as células são percorridas um total de n^4 vezes. Se tivermos uma matriz de 100x100, por exemplo, isso dá 100.000.000 de vezes. Se for 500x500, vai dar 62.500.000.000 vezes. O ideal seria não extrapolar muito do n^2.

Isso ocorre porque o seu algoritmo faz o seguinte:

  1. Marca todas as bordas que jogam para fora da matriz com X.

  2. Procura por células vizinhas que levem para células com X e as marca com X também. Cada etapa de procura demanda olhar para todas as n^2 células. Para garantir que isso acabe por marcar todas as células inseguras, propagando todos os Xs necessários, execute isso n^2 vezes.

Ocorre que esse algoritmo não é eficiente porque essa é uma forma bem lenta de propagar os X. No caso de após algumas iterações, o X parar de ser propagado, isso significa que qualquer iteração posterior não propagará mais nada. Ainda assim você insiste até que se esgote o número de iterações, ao invés de abortar o processo. Entretanto, o principal problema é que cada posição vai ser analisada um número n^2 de vezes, e a grande maioria dessas análises será repetitiva e vã.

Como resolver isso?

  • Podemos colocar as posições em que marcamos X em uma lista/fila, para analisar depois com o AnalisaVizinhos.

  • Ao analisar uma posição da lista, a retiramos da lista/fila.

  • Isso garante que uma mesma posição só entra na lista uma única vez e só é analisada uma única vez.

  • Quando a lista/fila ficar vazia, não precisaremos mais chamar o AnalisaVizinhos. Isso garante que rodadas extras e vãs após o resultado já estar definido não serão executadas.

  • Vez que uma posição é analisada uma única vez, essa variação do algoritmo vai executar n^2 vezes no pior caso, e não mais n^4 vezes em todos os casos.

  • Com tudo isso, na matriz 100x100 ao invés de fazer 100.000.000 iterações sempre, serão feitas apenas 10.000 no pior caso. Na matriz 500x500 ao invés de fazer um total de 62.500.000.000 iterações sempre, vamos fazer 250.000 no pior caso. Lembrando que o caso médio tende a ser bem menor que o pior caso.

Enfim, a ideia aqui é apenas rastrear quais são as posições que valem a pena ser analisadas e em qual ordem ao invés de simplesmente analisar todas cegamente um número bem grande de vezes.

É verdade que esse algoritmo é significativamente diferente do seu algoritmo original. Entretanto, não vejo forma de salvar o seu algoritmo original sem introduzir algumas mudanças significativas.

Aqui vai a implementação resultante:

#include <stdio.h>

char matriz[500][500];

// Esta função analisa as bordas e atribui X na matriz se elas indicarem que sai do tabuleiro
int AnalisaBordas(int linhas, int colunas, int *fila_linhas, int *fila_colunas) {
    int contador;
    int posicao_fila = 0;

    for (contador = 0; contador < colunas; contador++) {
        // Analisa a primeira linha.
        if (matriz[0][contador] == 'A') {
            matriz[0][contador] = 'X';
            fila_linhas[posicao_fila] = 0;
            fila_colunas[posicao_fila] = contador;
            posicao_fila++;
        }

        // Analisa a última linha.
        if (matriz[linhas - 1][contador] == 'V') {
            matriz[linhas - 1][contador] = 'X';
            fila_linhas[posicao_fila] = linhas - 1;
            fila_colunas[posicao_fila] = contador;
            posicao_fila++;
        }
    }

    for (contador = 0; contador < linhas; contador++) {
        // Analisa a primeira coluna.
        if (matriz[contador][0] == '<') {
            matriz[contador][0] = 'X';
            fila_linhas[posicao_fila] = contador;
            fila_colunas[posicao_fila] = 0;
            posicao_fila++;
        }

        // Analisa a última coluna.
        if (matriz[contador][colunas - 1] == '>') {
            matriz[contador][colunas - 1] = 'X';
            fila_linhas[posicao_fila] = contador;
            fila_colunas[posicao_fila] = colunas - 1;
            posicao_fila++;
        }
    }

    return posicao_fila;
}

// Esta função analisa os vizinhos da célula [i][j].
void AnalisaVizinhos(int i, int j, int *fila_linhas, int *fila_colunas, int *posicao_fila) {

    // Analisa a célula a direita.
    if (matriz[i][j + 1] == '<') {
        matriz[i][j + 1] = 'X';
        fila_linhas[*posicao_fila] = i;
        fila_colunas[*posicao_fila] = j + 1;
        (*posicao_fila)++;
    }

    // Analisa a célula a esquerda.
    if (matriz[i][j - 1] == '>') {
        matriz[i][j - 1] = 'X';
        fila_linhas[*posicao_fila] = i;
        fila_colunas[*posicao_fila] = j - 1;
        (*posicao_fila)++;
    }

    // Analisa a célula abaixo.
    if (matriz[i + 1][j] == 'A') {
        matriz[i + 1][j] = 'X';
        fila_linhas[*posicao_fila] = i + 1;
        fila_colunas[*posicao_fila] = j;
        (*posicao_fila)++;
    }

    // Analisa a célula acima.
    if (matriz[i - 1][j] == 'V') {
        matriz[i-  1][j] = 'X';
        fila_linhas[*posicao_fila] = i - 1;
        fila_colunas[*posicao_fila] = j;
        (*posicao_fila)++;
    }
}

void PropagaFila(int *fila_linhas, int *fila_colunas, int tamanho_inicial_fila) {
    int inicio_fila = 0;
    int fim_fila = tamanho_inicial_fila;
    while (inicio_fila < fim_fila) {
        AnalisaVizinhos(fila_linhas[inicio_fila], fila_colunas[inicio_fila], fila_linhas, fila_colunas, &fim_fila);
        inicio_fila++;
    }
}

// Loop para adicionar os caracteres.
void PreencherMatriz(int linhas, int colunas) {
    int linha, coluna;
    for (linha = 0; linha < linhas; linha++) {
        for (coluna = 0; coluna < colunas; coluna++) {
            char c;
            do {
                c = getchar();
            } while (c != '<' && c != '>' && c != 'V' && c != 'A');
            matriz[linha][coluna] = c;
        }
    }
}

// Loop para adicionar os caracteres.
int ContarMatriz(int linhas, int colunas) {
    int seguras = 0;
    int linha, coluna;
    for (linha = 0; linha < linhas; linha++) {
        for (coluna = 0; coluna < colunas; coluna++) {
            if (matriz[linha][coluna] != 'X') seguras++;
        }
    }
    return seguras;
}

int main() {
    int n;
    scanf("%d", &n);
    if (n <= 0 || n > 500) {
        printf("Tamanho invalido para a matriz");
        return 1;
    }

    PreencherMatriz(n, n);

    // Cria a fila.
    int fila_linhas[500];
    int fila_colunas[500];
    int i;
    for (i = 0; i < 500; i++) {
        fila_linhas[i] = fila_colunas[i] = -1;
    }

    int tamanho_inicial_fila = AnalisaBordas(n, n, fila_linhas, fila_colunas);
    PropagaFila(fila_linhas, fila_colunas, tamanho_inicial_fila);

    int seguras = ContarMatriz(n, n);

    printf("%d\n", seguras); // Exibe quantas posições são seguras.
    return 0;
}

Veja aqui funcionando no ideone.

Note que eu separei o conceito de linhas e colunas na maioria das funções para que o algoritmo funcione com quaisquer matrizes retangulares, mesmo as não-quadradas.

Há algumas melhorias possíveis, para evitar ter que ter a matriz como uma variável global, simplificar a repetição de códigos e melhor encapsular e modularizar tanto a fila quanto a matriz dentro de estruturas de dados especializadas. Entretanto, o algoritmo básico continuaria o mesmo.

1
  • 1
    Muito obrigado cara...melhorou muito essas dicas!!! E esse código aí me ajudou bastante!!!
    – Abism
    Commented 4/11/2016 às 17:15

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .