Dá para fazer várias melhorias. Vamos começar pelas mais simples:
Evite usar variavel = variavel + 1
. É mais simples e menos propenso a erros usar variavel++
.
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.
Não declare o retorno como int
se o valor retornado não for utilizado para nada. Utilize void
nesse caso.
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.
Utilize as chaves nos laços for
e nos if
s. Para entender o porquê, veja o trecho dessa minha outra resposta que tem o título "Chaves após if
, else
, while
e for
".
É 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 for
s aninhados um dentro do outro. O externo percorre células (onde é o tamanho do quadrado), enquanto que cada um dos laços internos também percorre vezes (um para a altura e outro para a largura). Assim sendo, as células são percorridas um total de 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 .
Isso ocorre porque o seu algoritmo faz o seguinte:
Marca todas as bordas que jogam para fora da matriz com X
.
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 células. Para garantir que isso acabe por marcar todas as células inseguras, propagando todos os X
s necessários, execute isso 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 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 vezes no pior caso, e não mais 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.