TÓPICO
PROBLEM 1100 - URI Fórum 1.0
Este tópico foi resolvido e não pode receber novas respostas.
-
crbonilha respondido on jan. 29 2014
O seu algoritmo está correto, você só não soube tratar o fim de arquivo. Tente assim:
while(scanf("%s",ini) != EOF)Se quiser um conselho, o algoritmo de Dijkstra é recomendado quando você tem arestas de valores distintos, e para este exercício em questão, onde o custo de um salto é sempre 1, uma simples BFS seria mais fácil de implementar, e até mais eficiente.
-
gvdfarias respondido 8 years ago
#include <bits/stdc++.h> using namespace std; int xx,yy,x,y,matriz[10][10]; struct cord{ int x; int y; int i; }; vector<cord> dfs; void coloca(int a,int b,int c){ cord aux; c++; aux.x=a+2; aux.y=b+1; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a+1; aux.y=b+2; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a-2; aux.y=b+1; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a-1; aux.y=b+2; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a+2; aux.y=b-1; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a+1; aux.y=b-2; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a-2; aux.y=b-1; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); aux.x=a-1; aux.y=b-2; aux.i=c; if(aux.x>0 && aux.x<9 && aux.y>0 && aux.y<9) dfs.push_back(aux); } void dfsF(){ while(dfs.size()>0){ cord aux = dfs.back(); dfs.pop_back(); if(matriz[aux.x][aux.y]==0 || matriz[aux.x][aux.y]>aux.i){ matriz[aux.x][aux.y]=aux.i; if(aux.x!=xx && aux.y!=y) coloca(aux.x,aux.y,aux.i); } } } int main(){ char c1,c2; while(scanf("\n%c%d %c%d",&c1,&y,&c2,&yy)!=EOF){ char aa=c1,bb=c2; x = ((int) c1)-96; xx = ((int) c2)-96; for(int i=0;i<9;i++) for(int j=0;j<9;j++) matriz[i][j]=0; cord au; au.x=x; au.y=y; au.i=0; dfs.push_back(au); coloca(x,y,0); dfsF(); printf("To get from %c%d to %c%d takes %d knight moves.\n", aa,y,bb,yy,matriz[xx][yy]); } return 7; }Porque estou levando 10%WA?
-
hpdserrano respondido 7 years ago
Alguém poderia me ajudar a entender o porquê do meu código estar recebendo WA(10%)?
Oops, resolvido -
asensolo respondido 9 years ago
Boa tarde!
Estou recebendo Time limit exceeded, porém nos meus testes o tempo de execução não excedeu 1s...
Será que o problema está no EOF?
Obrigado !!
#include <iostream> #include <vector> using namespace std; class Grafo { public: vector<vector<int> > arestas; vector<vector<double> > pesos; Grafo(int nro_vertices) { arestas.resize(nro_vertices, vector<int>(0, 0)); pesos.resize(nro_vertices, vector<double>(0, 0)); } void insereAresta(int origem, int destino, bool direcionado, double peso) { unsigned int maxIndex; if (origem > destino) maxIndex = origem + 1; else maxIndex = destino + 1; if (maxIndex > arestas.size()) { arestas.resize(maxIndex, vector<int>(0, 0)); pesos.resize(maxIndex, vector<double>(0, 0)); } arestas[origem].push_back(destino); pesos[origem].push_back(peso); if (!direcionado) insereAresta(destino, origem, true, peso); } void buscaMenorCaminho(int verticeInicial, int verticeFinal, vector<int>* ordemVisitas, vector<double>* distancia) { unsigned int contador = arestas.size(); vector<bool> visitado (arestas.size(), false); ordemVisitas->resize(arestas.size(), -1); distancia->resize(arestas.size(), -1); distancia->at(verticeInicial) = 0; while (contador > 0) { int menor = calculoMC(&visitado, distancia); if (menor == -1) break; if (visitado.at(verticeFinal) == true) break; visitado[menor] = true; contador--; for (unsigned int x = 0; x < arestas[menor].size(); x++) { int ind = arestas[menor][x]; if (distancia->at(ind) < 0) { distancia->at(ind) = distancia->at(menor) + pesos[menor][x]; ordemVisitas->at(ind) = menor; } else { if (distancia->at(ind) > distancia->at(menor) + pesos[menor][x]) { distancia->at(ind) = distancia->at(menor) + pesos[menor][x]; ordemVisitas->at(ind) = menor; } } } } } private: int calculoMC(vector<bool>* visitado, vector<double>* distancia) { int menor = -1; bool primeiro = true; for (unsigned int x = 0; x < visitado->size(); x++) { if (distancia->at(x) >= 0 && !visitado->at(x)) { if (primeiro) { menor = x; primeiro = false; } else { if(distancia->at(menor) > distancia->at(x)) menor = x; } } } return menor; } }; int main() { Grafo gr(65); for (int l = 1; l <= 8; l++) { for (int c = 1; c <= 8; c++) { if (l - 2 >= 1) { if (c - 1 >= 1) gr.insereAresta(((l - 1) * 8) + c, (l - 3) * 8 + (c - 1), true, 1); if (c + 1 <= 8) gr.insereAresta(((l - 1) * 8) + c, (l - 3) * 8 + (c + 1), true, 1); } if (l + 2 <= 8) { if (c - 1 >= 1) gr.insereAresta(((l - 1) * 8) + c, (l + 1) * 8 + (c - 1), true, 1); if (c + 1 <= 8) gr.insereAresta(((l - 1) * 8) + c, (l + 1) * 8 + (c + 1), true, 1); } if (c - 2 >= 1) { if (l - 1 >= 1) gr.insereAresta(((l - 1) * 8) + c, (l - 2) * 8 + (c - 2), true, 1); if (l + 1 <= 8) gr.insereAresta(((l - 1) * 8) + c, (l + 0) * 8 + (c - 2), true, 1); } if (c + 2 <= 8) { if (l - 1 >= 1) gr.insereAresta(((l - 1) * 8) + c, (l - 2) * 8 + (c + 2), true, 1); if (l + 1 <= 8) gr.insereAresta(((l - 1) * 8) + c, (l + 0) * 8 + (c + 2), true, 1); } } } char orig[2], dest[2]; while (cin >> orig[0] >> orig[1] >> dest[0] >> dest[1]) { vector<double> peso; vector<int> caminho; gr.buscaMenorCaminho(((((int)(orig[1]) - 49) * 8) + (int)(orig[0]) - 96), ((((int)(dest[1]) - 49) * 8) + (int)(dest[0]) - 96), &caminho, &peso); cout << "To get from " << orig[0] << orig[1] << " to " << dest[0] << dest[1]; cout << " takes " << peso.at(((((int)(dest[1]) - 49) * 8) + (int)(dest[0]) - 96)); cout << " knight moves." << endl; } return 0; } -
DamiHenrique respondido on jan. 30 2014
Que estranho, sempre usei assim em todos problemas envolvendo strings e EOF aqui no uri... oO Mas era realmente isso... Obrigado pela dica. =)
-
DamiHenrique respondido on jan. 28 2014
Bom dia!
Alguém poderia me dizer se é realmente p esse código tomar TLE? Sendo que como considerei, temos apenas 64 vertices.. Ou estou viajando demais? :P
Aceito!
