Skip to Content
CTRL K

Why Did the Cow Cross the Road

Análisis oficial (C++) 

Solución

En lugar de tratar esto como un problema de grilla, intentemos encararlo como un problema de grafos con nodos y aristas.

Primero observamos que las dos casillas intermediarias que Bessie usó para viajar en realidad no importan porque Bessie solo se da un festín en las casillas de pasto cada 3 movimientos y el tiempo para viajar entre casillas adyacentes es una constante TT. Así que queremos formar una arista directa entre cada casilla que esté a exactamente 3 distancias de Manhattan, con un peso de

{The time to feast the target grass tile}+3∗T\{\text{The time to feast the target grass tile}\} + 3 * T

Sin embargo, si la casilla en la que Bessie acaba de darse un festín está a menos de 3 unidades (usando distancia de Manhattan) de la casilla de Farmer John, entonces sería más deseable que Bessie viaje a Farmer John directamente que tomar otra casilla a distancia 3. Así que también formamos una arista directa entre esas dos casillas con un peso de

{The manhattan distance}∗T\{\text{The manhattan distance}\} * T

Implementación

Complejidad temporal: O(N2log⁡N)\mathcal{O}(N^{2} \log{N})

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ss second
 
// Posibles direcciones en las que Bessie puede ir a comer pasto
int dx[] = {1, 0, -1, 0, 3, 0, -3, 0, 2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {0, 1, 0, -1, 0, 3, 0, -3, 1, -1, 2, -2, 2, -2, 1, -1};
 
int main() {
	ifstream fin("visitfj.in");
 
	int n, t;
	fin >> n >> t;
	vector<vector<int>> field(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { fin >> field[i][j]; }
	}
 
	// grilla 2d de enteros inicializada con valores máximos para distancia
	vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
	// grilla 2d booleana inicializada en false para rastrear visitas
	vector<vector<bool>> visited(n, vector<bool>(n));
	// {distancia, {fila, col}}
	priority_queue<pair<int, pii>> dijkstra;
	dijkstra.push(make_pair(0, make_pair(0, 0)));
	dist[0][0] = 0;
	while (!dijkstra.empty()) {
		int x, y;
		tie(x, y) = dijkstra.top().ss;
		dijkstra.pop();
 
		// comprobar si esta coordenada ya fue visitada
		if (visited[x][y]) { continue; }
		visited[x][y] = true;
		for (int i = 0; i < 16; i++) {
			int newx = x + dx[i], newy = y + dy[i];
			// comprobar si esta nueva ubicación está fuera de los límites
			if (newx < 0 || newx >= n || newy < 0 || newy >= n) { continue; }
			// actualizar la distancia más corta a esta nueva ubicación
			if (dist[newx][newy] > dist[x][y] + 3 * t + field[newx][newy]) {
				dist[newx][newy] = dist[x][y] + 3 * t + field[newx][newy];
				dijkstra.push(make_pair(-dist[newx][newy], make_pair(newx, newy)));
			}
		}
 
		int manhattan = n - x - 1 + n - y - 1;
		if (manhattan < 3) {
			dist[n - 1][n - 1] = min(dist[n - 1][n - 1], dist[x][y] + manhattan * t);
		}
	}
 
	ofstream("visitfj.out") << dist[n - 1][n - 1] << endl;
}
import java.io.*;
import java.util.*;
 
public class VisitFJ {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("visitfj");
 
		// Posibles caminos que la vaca puede tomar
		int[] dx = {0, 1, 2, 3, 0, 1, 2, -1, -2, -3, -1, -2, 1, -1, 0, 0};
		int[] dy = {3, 2, 1, 0, -3, -2, -1, 2, 1, 0, -2, -1, 0, 0, 1, -1};
 
		int N = io.nextInt();
		int T = io.nextInt();
 
		int[][] w = new int[N][N];
		int[][] dist = new int[N][N];
 
		for (int i = 0; i < N; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
			for (int j = 0; j < N; j++) { w[i][j] = io.nextInt(); }
		}
 
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(new int[] {0, 0}, 0));
		while (!pq.isEmpty()) {
			Edge cur = pq.poll();
			int[] pos = cur.t;
 
			int d = N - 1 - pos[0] + N - 1 - pos[1];
 
			// Si está a menos de 3 bloques, actualizar el peso mínimo necesario
			if (d < 3 && d > 0) {
				dist[N - 1][N - 1] = Math.min(dist[N - 1][N - 1], cur.w + T * d);
			}
 
			for (int i = 0; i < dx.length; i++) {
				int nx = pos[0] + dx[i];
				int ny = pos[1] + dy[i];
 
				// Continuar si el nuevo punto está fuera de los límites
				if (nx < 0 || nx >= N || ny < 0 || ny >= N) { continue; }
 
				int nw = cur.w + w[nx][ny] + T * 3;
 
				// Si la nueva distancia es mayor que la distancia mínima actual,
				// no se necesita
				if (nw > dist[nx][ny]) { continue; }
				dist[nx][ny] = nw;
 
				pq.add(new Edge(new int[] {nx, ny}, nw));
			}
		}
 
		io.println(dist[N - 1][N - 1]);
		io.close();
	}
 
	private static class Edge implements Comparable<Edge> {
		int[] t;
		int w;
		public Edge(int[] t, int w) {
			this.t = t;
			this.w = w;
		}
 
		@Override
		public int compareTo(Edge o) {
			return w - o.w;
		}
	}
 
	// CodeSnip{Kattio}
}
Fundamentos