QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125217#4970. Panda Hunting Treasure BoxAH_LushoWA 1ms3448kbC++143.3kb2023-07-16 06:46:362023-07-16 06:46:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 06:46:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3448kb
  • [2023-07-16 06:46:36]
  • 提交

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'