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?