QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125217 | #4970. Panda Hunting Treasure Box | AH_Lusho | WA | 1ms | 3448kb | C++14 | 3.3kb | 2023-07-16 06:46:36 | 2023-07-16 06:46:39 |
Judging History
answer
#include <bits/stdc++.h> // Para importar todas librerias
#define input freopen("in.txt", "r", stdin)
#define output freopen("out.txt", "w", stdout)
#define INF 100000010 // 1e9
using namespace std;
int dx[] = {-1,-1,-1,0,1,1,1,0};
int dy[] = {-1,0,1,1,1,0,-1,-1};
// Estructura para representar un nodo del grafo
struct Node {
int x;
int y;
int weight;
};
// Función para verificar si un nodo está dentro de los límites del grafo
bool isValid(int x, int y, int rows, int cols) {
return (x >= 0 && x < rows && y >= 0 && y < cols);
}
// Función de Dijkstra para encontrar la ruta más corta en un grafo
int dijkstra(vector<vector<int>>& graph, int sourceX, int sourceY, int rows, int cols, int e) {
// Crear una matriz para almacenar las distancias mínimas desde la fuente
vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
// Crear una matriz para almacenar el estado de visita de los nodos
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
// Comparador personalizado para la cola de prioridad
auto cmp = [](const Node& a, const Node& b) {
return a.weight > b.weight;
};
int res = 0;
// Crear una cola de prioridad para seleccionar el nodo con la distancia mínima
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
// Establecer la distancia de la fuente a 0
distance[sourceX][sourceY] = 0;
// Insertar la fuente en la cola de prioridad
pq.push({ sourceX, sourceY, 0 });
// Realizar el algoritmo de Dijkstra
while (!pq.empty()) {
// Extraer el nodo con la menor distancia de la cola de prioridad
Node currentNode = pq.top();
pq.pop();
int x = currentNode.x;
int y = currentNode.y;
// Marcar el nodo como visitado
visited[x][y] = true;
if (distance[x][y] > e) break;
if (graph[x][y] != 0) {
res = max(res, graph[x][y]);
continue;
}
// Comprobar todas las direcciones posibles (horizontal, vertical y diagonales)
for (int i = 0; i < 8; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
// Verificar si la nueva posición está dentro de los límites y no está visitada
if (isValid(newX, newY, rows, cols) && !visited[newX][newY]) {
// Calcular el peso acumulado desde el nodo actual hasta el siguiente nodo
int weight = distance[x][y] + i + 1;
// Si el peso acumulado es menor que la distancia actual almacenada, actualizarla
if (weight < distance[newX][newY]) {
distance[newX][newY] = weight;
// Insertar el nuevo nodo en la cola de prioridad
pq.push({ newX, newY, weight });
}
}
}
}
// Devolver la matriz de distancias mínimas
return res;
}
int main()
{
// input;
// output;
int r,c;
cin>>r>>c;
int x,y,e;
cin>>x>>y>>e;
vector<vector<int>> graph(r, vector<int>(c));
for(int i = 0; i<r;i++) {
for(int j=0; j<c ; j++) {
cin>>graph[i][j];
}
}
cout<<dijkstra(graph,x,y,r,c,e);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3448kb
input:
5 6 1 1 55 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 10 0 1 0 0 1 9 1 0 0 0 1
output:
10
result:
wrong answer 1st lines differ - expected: '1', found: '10'