TÓPICO

PROBLEM 1621 - URI Fórum 1.0

URI Online Judge perguntou 6 years ago

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

  • Paulo Felipe respondido 5 years ago

    você tem que aproveitar a própria estrutura da matriz para não fazer a lista de adjacência, fazer o vetor de marcação igual a estrutura da matriz também é válido para ganhar tempo sem realização de operações.

  • Ronaldo respondido 5 years ago

    Então acho que essa parte eu entendi, tentei fazer e deu TLE, procurei sobre o problema e achei um editorial do criador do problema, resolvi de outro jeito tentei vários casos de testes e passou exatamente como no toolkit entretanto estou recebendo WA 100%

    #include<bits/stdc++.h>
using namespace std;

#define Vertex int
#define maxV 250001
static int dist[maxV];
static int lbl[maxV];
struct digraph {
   int V;
   int A;
   int **adj;
};
typedef struct digraph *Digraph;
int **MATRIXint( int r, int c, int val) {
   Vertex i, j;
   int **m = (int **) malloc( r * sizeof (int *));
   for (i = 0; i < r; i++)
      m[i] = (int *) malloc( c * sizeof (int));
   for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
         m[i][j] = val;
   return m;
}
Digraph DIGRAPHinit( int V) {
   Digraph G = (digraph *) malloc( sizeof *G);
   G->V = V;
   G->A = 0;
   G->adj = MATRIXint( V, V, 0);
   return G;
}
void DIGRAPHinsertA( Digraph G, Vertex v, Vertex w) {
   if (G->adj[v][w] == 0) {
      G->adj[v][w] = 1;
      G->adj[w][v] = 1;
      G->A+=2;
   }
}
void DIGRAPHdist(Digraph G, Vertex s)
{
   const int INFINITO = -1;
   queue<int> pilha;
   Vertex v, w;
   for (v = 0; v < G->V; v++)
      dist[v] = INFINITO;
   dist[s] = 0;
    pilha.push(s);
   while (!pilha.empty()) {
      v = pilha.front();
      pilha.pop();
      for (w = 0; w < G->V; w++)
         if (G->adj[v][w] == 1 && dist[w] == INFINITO) {
            dist[w] = dist[v] + 1;
            pilha.push(w);
         }
   }
}
int main()
{
    int n, m, resp, V;
    vector<int>v;
    int cont, M[501][501];
    char S[501];
    scanf("%d%d", &n, &m);
    while(n > 0 && m > 0)
    {
        v.clear();
        Digraph G = DIGRAPHinit(n*m + 1);
        cont = 1;
        for(int j = 1; j <= n; j++)
        {
            getchar();
            for(int k = 1; k <= m; k++)
            {
                V = getchar();
                S[k] = (char) V;
                if(S[k] == '.') {
                        //cout << "M[j-1][k] = " << M[j-1][k] << " M[j][k-1] = " << M[j][k-1] << endl;
                        if(M[j-1][k] > 0 && j - 1 > 0){
                            //cout << "Aresta v = " << cont << " w = " << M[j-1][k] << endl;
                            DIGRAPHinsertA(G, cont, M[j-1][k]);
                        }

                        if(M[j][k-1] > 0 && k - 1 > 0)
                        {
                            //cout << "Aresta v = " << cont << " w = " << M[j][k-1] << endl;
                            DIGRAPHinsertA(G, cont, M[j][k-1]);
                        }

                        M[j][k] = cont;
                        v.push_back(cont);
                }
                else
                {
                    M[j][k] = 0;
                }
                cont++;
            }
        }
        resp = 0;
        int dist1;
        DIGRAPHdist(G, v[0]);
        for(int i = 0; i < v.size(); i++)
        {
            if(dist[v[i]] > 0)
            {
                if(resp < dist[v[i]])
                {
                    resp = dist[v[i]];
                    dist1 = v[i];
                }
            }
        }
        DIGRAPHdist(G, dist1);
        for(int i = 0; i < v.size(); i++)
        {
            if(dist[v[i]] > 0)
            {
                if(resp < dist[v[i]])
                {
                    resp = dist[v[i]];
                }
            }
        }
        printf("%d\n", resp);
        scanf("%d%d", &n, &m);
    }
    return 0;
}

  • Dâmi Henrique respondido 5 years ago

    Fala Ronaldo..

    Nesse tipo de problema você tem um grafo implícito, não há a necessidade de armazenar ele em uma lista ou matriz de adjacência, por exemplo...

    Você considera vértice, cada posição da matriz, por exemplo linha 2, coluna 3, é um vértice. Agora as arestas, nesse problema em particular, como você só pode "andar" na horizontal e vertical, é como se você tivesse uma aresta para cada um desses 4 esses vizinhos(atentar no caso de estar em uma borda).

    Ex: Estou na posição [2][3] da minha matriz, então implicitamente tenho arestas para as posições: [2][4], [2][2], [1][3] e [3][3].

    Não sei se ficou muito claro, qualquer coisa é só falar..

  • Ronaldo respondido 5 years ago

    Eu estou tendo um pouco de dificuldade para ler o grafo, o que eu considero com vértice e o que eu considero como arco? Alguém me da uma ajuda com isso ai?