OJ Board

Code: Select all

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};

#define	INF			1000000000

const int MAXN = 1000 * 1000 + 1 ; 
int R , C ; 
int w[1002*1002];
bool out[1002*1002];

int	dist[MAXN];
int	heap[MAXN + 1];
int	scratch[MAXN + 1];
int	heap_size;

void update_heap(int u)
{
	int	q = scratch[u],p;
	
	while(q > 1)
	{
		p = q / 2;
		
		if(dist[heap[q]] < dist[heap[p]])
		{
			swap(scratch[heap[p]],scratch[heap[q]]);
			swap(heap[p],heap[q]);
			q = p;
		}
		else
			break;
	}
}

void heapify(int i)
{
	int	q = i,m;
	
	while(true)
	{
		m = q;
		
		if(2 * q <= heap_size && dist[heap[2 * q]] < dist[heap[m]])
			m = 2 * q;
		
		if(2 * q + 1 <= heap_size && dist[heap[2 * q + 1]] < dist[heap[m]])
			m = 2 * q + 1;
		
		if(m != q)
		{
			swap(scratch[heap[q]],scratch[heap[m]]);
			swap(heap[q],heap[m]);
			q = m;
		}
		else
			break;
	}
}

int src , dest  ; 
int main(){
	
	int kase , i , u,v,c , r , cost , nr , nc ; 
	scanf("%d",&kase);
	
	while(kase--)
	{
		scanf("%d %d",&R,&C);
		for(i=0;i<R*C;++i){
			scanf("%d",&w[i]);
			out[i] = false ;
			dist[i]		= INF;
			scratch[i]	= i + 1;
			heap[i + 1]	= i;
		}
		heap_size = R * C ; 
		src = 0 ; dest = R * C - 1 ; 
		
		
		dist[src] = w[0];
		update_heap(src);
		
		while(heap_size > 1)
		{
			u = heap[1];
			if(u==dest)break ; 	
			scratch[heap[heap_size]] = 1;
			heap[1] = heap[heap_size];
			heap_size--;
			heapify(1);
			out[u] = true ; 
			c = u % C ; r = u / C ; 
			for(i=0;i<4;++i){
				nr = r + dr[i] ; 
				nc = c + dc[i] ; 
				if((nr<0||nr>=R) || (nc<0||nc>=C))continue ; 
				v = nr * C + nc ; 
				if(out[v])continue ;
				cost = dist[u] + w[v] ; 
				if( cost < dist[v] ){
					dist[v] =cost ; 
					update_heap(v) ; 
				}
			
			}
			
		}
		printf("%d\n",dist[dest]);
	}
	
	return 0 ; 
}

Code: Select all

public static final int agua = -1;
public static final int libre = 1;
public static final int fueraPantano = -2;
public static final int enteroMaximo = 999999;
public static final int energia[][] = { { 7, 6, 5, 6, 7 },{ 6, 3, 2, 3, 6 },
									    { 5, 2, 0, 2, 5 },{ 6, 3, 2, 3, 6 },
										{ 7, 6, 5, 6, 7 } };
										
PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
										
public static void main(String[] args) {
	int c = 0, r = 0, cs = 0, rs = 0, ct = 0, rt = 0, b;
	int c1, r1, c2, r2;
	int i, j, k;
	int[][] pantano = null;
	int[][] costo = null;
	Scanner in = new Scanner(System.in);
	// leer las dimensiones del pantano
	c = in.nextInt();
	r = in.nextInt();
	while (c > 0) {
		// crear el pantano y matriz de costos
		pantano = new int[r + 4][c + 4];
		costo = new int[r + 4][c + 4];
		// indicar que la fila 0 y columa 0
		// estan fuera del pantano
		for (i = 0; i < c + 4; i++)
			pantano[0][i] = pantano[1][i] = fueraPantano;
		for (i = 0; i < r + 4; i++)
			pantano[i][0] = pantano[i][1] = fueraPantano;
		for (i = 2; i < c + 4; i++)
			pantano[r + 2][i] = pantano[r + 3][i] = fueraPantano;
		for (i = 2; i < r + 4; i++)
			pantano[i][c + 2] = pantano[i][c + 3] = fueraPantano;
		// Marcar las celdas del pantano como libres
		// y los costos como un entero grande
		for (i = 2; i < r + 2; i++) {
			for (j = 2; j < c + 2; j++) {
				pantano[i][j] = libre;
				costo[i][j] = enteroMaximo;
			}
		}
		// leer el origen y el destino
		cs = in.nextInt();
		rs = in.nextInt();
		ct = in.nextInt();
		rt = in.nextInt();
		// leer el numero de zonas acuosas
		b = in.nextInt();
		for (i = 0; i < b; i++) {
			// leer las cordenadas de la region
			c1 = in.nextInt();
			r1 = in.nextInt();
			c2 = in.nextInt();
			r2 = in.nextInt();
			c1 += 1;
			c2 += 1;
			r1 += 1;
			r2 += 1;
			for (k = r1; k <= r2; k++) {
				for (j = c1; j <= c2; j++) {
					pantano[k][j] = agua;
				}
			}
		}
		cs++;
		rs++;
		ct++;
		rt++;
		// ver(pantano,r, c);
		// ver(costo,r, c);
		dijkstra(pantano, costo, rs, cs, rt, ct);
		if (costo[rt][ct] < enteroMaximo)
			System.out.println(costo[rt][ct]);
		else
			System.out.println("Impossible");
		c = in.nextInt();
		r = in.nextInt();
	}
}

public static void dijkstra(int[][] pantano, int[][] costo,int rs, int cs,int rt, int ct) {
	int rv, cv; int i, j;
	Nodo filcol;
	PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
	costo[rs][cs] = 0;
	rv = rs;
	cv = cs;
	cp.add(new Nodo(0, rs, cs));
	while (!cp.isEmpty()) {
		filcol = cp.remove();
		rv = filcol.fila;
		cv = filcol.col;
		for (i = -2; i < 3; i++) {
			for (j = -2; j < 3; j++) {
				if (pantano[rv + i][cv + j] == libre) {
					if (costo[rv + i][cv + j] > (costo[rv][cv] + energia[i + 2][j + 2])) {
						costo[rv + i][cv + j] = costo[rv][cv] + energia[i + 2][j + 2];
						cp.add(new Nodo(costo[rv + i][cv + j],rv + i, cv + j));
					}
				}
			}
		}
	}
}

class Nodo implements Comparable<Nodo> {
	int costo, fila, col;
	
	public Nodo(int costo, int fila, int col) {
		this.costo = costo;
		this.fila = fila;
		this.col = col;
	}
	
	public int compareTo(Nodo other) {
		return costo - other.costo;
	}
}