You can make several improvements. Let’s start with the simplest:
Avoid using variavel = variavel + 1. It is simpler and less prone to errors use variavel++.
Avoid using global variables as they are considered a bad programming practice for several reasons. Use function parameters. In the example below I only left the matrix as global, because putting it as a parameter would make things much more complicated, although it is perfectly possible anyway.
Do not declare the return as int if the returned value is not used for anything. Use void in that case.
Remember that in C, the first position is position 0, not position 1. In your algorithm you are allocating, but you are not using position 0.
Use keys on loops for and us ifs. To understand why, see of my other answer entitled "Keys after if, else, while and for".
It is possible to place some of the tasks that are within your main in specialised functions in order to better organise the code.
Your algorithm has 3 fornestled within each other. The outer travels 
cells (where 
is the size of the square), while each of the internal links also travels times (one for height and one for width). Thus, cells are traversed a total of 
times. If we have a 100x100 matrix, for example, that’s 100,000,000 times. If it’s 500x500, it’s 62,500,000,000 times. The ideal would be not to extrapolate too much from .
This is because your algorithm does the following:
Marks all edges that throw out the matrix with X.
Search for neighboring cells that lead to cells with X and marks them with X also. Each step of demand demand look for all cells. To ensure that this ultimately marks all unsafe cells, propagating all Xs necessary, perform this times.
It turns out that this algorithm is not efficient because this is a very slow way to propagate X. In the case of some iterations, the X stop being propagated, it means that any subsequent iteration will not propagate anything else. Still you insist until the number of iterations runs out, rather than aborting the process. However, the main problem is that each position will be analyzed a number at times, and the vast majority of these analyses will be repetitive and vain.
How to solve this?
We can put the positions we scored on X in a list/queue, to be analyzed later with the AnalisaVizinhos.
When analyzing a position from the list, we remove it from the list/queue.
This ensures that the same position only enters the list once and is only analyzed once.
When the list/queue is empty, we no longer need to call AnalisaVizinhos. This ensures that extra and empty rounds after the result is already set will not run.
Once a position is analyzed once, this variation of the algorithm will perform times worst-case, and no more times in all cases.
With all this, on the 100x100 matrix instead of making 100,000,000 iterations at all times, only 10,000 will be made worst-case. In the 500x500 matrix instead of making a total of 62,500,000,000 iterations at all times, let’s make 250,000 worst-case. Recalling that the average case tends to be much smaller than the worst case.
Anyway, the idea here is just to track down which positions are worth analyzing and in which order instead of just blindly analyzing them all a very large number of times.
It is true that this algorithm is significantly different from its original algorithm. However, I see no way to save your original algorithm without introducing some significant changes.
Here is the resulting implementation:
#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;
}
See here working on ideone.
Note that I have separated the concept of rows and columns into most functions for the algorithm to work with any rectangular matrices, even non-square ones.
There are some possible improvements, to avoid having to have the matrix as a global variable, simplify code repetition and better encapsulate and modularize both the queue and the matrix within specialized data structures. However, the basic algorithm would remain the same.
Why do your functions return int if the value is not used for anything?
– Pablo Almeida
But that’s what’s influencing ?
– Abism
Probably not, it was just an observation. It’s more like the problem is this triple loop of yours.
– Pablo Almeida
Because in the worst case the first is 500*500 there is a lot to go through, because he analyzes and if he finds an X he calls the function to analyze the neighbors what is taking...so I wonder if it can improve to do this in less time or something like that
– Abism
This looks like it looks better with dynamic programming, since whenever a square is considered unsafe, all those pointing to it are also unsafe, so the result of it can be reused.
– Pablo Almeida