HackerRank Huarongdao Problem Solution

In this post, we will solve HackerRank Huarongdao Problem Solution.

Huarongdao is a well-known game in China. The purpose of this game is to move the Cao Cao block out of the board.

Acme is interested in this game, and he invents a similar game. There is a N*M board. Some blocks in this board are movable, while some are fixed. There is only one empty position. In one step, you can move a block to the empty position, and it will take you one second. The purpose of this game is to move the Cao Cao block to a given position. Acme wants to finish the game as fast as possible.

But he finds it hard, so he cheats sometimes. When he cheats, he spends K seconds to pick a block and put it in an empty position. However, he is not allowed to pick the Cao Cao block out of the board .

Note

Immovable blocks cannot be moved while cheating.
A block can be moved only in the directions UP, DOWN, LEFT or RIGHT.

Input Format

The first line contains four integers N, M, K, Q separated by a single space. N lines follow.
Each line contains M integers 0 or 1 separated by a single space. If the j_th integer is 1, then the block in i_th row and j_th column is movable. If the j_th integer is 0 then the block in i_th row and j_th column is fixed. Then Q lines follows, each line contains six integers EX_i, EY_i, SX_i, SY_i, TX_i, TY_i separated by a single space. The i_th query is the Cao Cao block is in row SX_i column SY_i, the exit is in TX_i, TY_i, and the empty position is in row EX_i column EY_i. It is guaranteed that the blocks in these positions are movable. Find the minimum seconds Acme needs to finish the game. If it is impossible to finish the game, you should answer -1.

Constraints

N,M ≤ 200
1 ≤ Q ≤ 250
10 ≤ K≤ 15
1 ≤ EX_i, SX_i, TX_i≤ N
1 ≤ EY_i, SY_i,TY_i ≤ M

Output Format

You should output Q lines, i-th line contains an integer which is the answer to i-th query.

Sample Input

5 5 12 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 1 1
0 1 0 1 1
1 5 4 3 4 1

Sample Output

Explanation

Move the block in (1, 4) to (1, 5);
Move the block in (1, 3) to (1, 4);
Move the block in (1, 2) to (1, 3);
Move the block in (2, 2) to (1, 2);
Move the block in (3, 2) to (2, 2);
Move the block in (4, 2) to (3, 2);
Move the block in (4, 3) to (4, 2);
Move the block in (4, 1) to (4, 3) by cheating;
Move the block in (4, 2) to (4, 1).

So, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 12 + 1 = 20.

Table of Contents

Huarongdao C Solution

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <stddef.h>
#include <unistd.h>
#include <sys/time.h>
#include <math.h>
#include <stdint.h>
#include <ctype.h>

#ifdef __MACH__
#include <mach/clock.h>
#include <mach/mach.h>
#else
#include <time.h>
#include <stdarg.h>
#endif

#if 1
#ifndef LONG_LONG_MAX
#define LONG_LONG_MAX LONG_MAX
#endif

#define CACA_COMUN_TAM_MAX_LINEA (16*200000)
#define CACA_LOG_MAX_TAM_CADENA 2000

#define CACA_COMUN_BUF_STATICO (char[1000] ) { '\0' }

#define BITCH_VECTOR_NUM_BITS (sizeof(bitch_vector) * 8)

#define CACA_COMUN_ASSERT_DUROTE 0
#define CACA_COMUN_ASSERT_SUAVECITO 1
#define CACA_COMUN_ASSERT_NIMADRES 2

#define CACA_COMUN_VALOR_INVALIDO ((tipo_dato)UINT_MAX)
#define CACA_COMUN_IDX_INVALIDO ((natural)UNIVERGA_VALOR_INVALIDO)

typedef unsigned int natural;
typedef natural tipo_dato;
typedef long long entero_largo;
typedef unsigned long long entero_largo_sin_signo;
typedef unsigned long long bitch_vector;
typedef char byteme;

typedef enum BOOLEANOS {
	falso = 0, verdadero
} bool;

/*
 #define CACA_COMUN_TIPO_ASSERT CACA_COMUN_ASSERT_SUAVECITO
 */
#define CACA_COMUN_TIPO_ASSERT CACA_COMUN_ASSERT_DUROTE

#define assert_timeout_dummy(condition) 0;

#if CACA_COMUN_TIPO_ASSERT == CACA_COMUN_ASSERT_DUROTE
#define assert_timeout(condition) assert(condition);
#endif
#if CACA_COMUN_TIPO_ASSERT == CACA_COMUN_ASSERT_SUAVECITO
#define assert_timeout(condition) if(!(condition)){sleep(10);abort();}
#endif
#if CACA_COMUN_TIPO_ASSERT == CACA_COMUN_ASSERT_NIMADRES
#define assert_timeout(condition) 0
#endif

#define caca_log_debug(formato, args...) 0;

#define caca_comun_max(x,y) ((x) < (y) ? (y) : (x))
#define caca_comun_min(x,y) ((x) < (y) ? (x) : (y))

#endif

#define HV_MAX_LLAVE (200|((200)<<8))
#define HV_MAX_LLAVE_RODEADA (204|((204)<<8))

#if 1

#define BITCH_VALOR_INVALIDO CACA_COMUN_VALOR_INVALIDO

typedef struct bitch_vector_ctx {
	natural bitch_numeros_agregados_tam;
	bitch_vector *bitch_mapa;
} bitch_vector_ctx;

static inline bitch_vector_ctx *bitch_init(natural max_nums) {
	bitch_vector_ctx *bvctx = NULL;
	bvctx = calloc(1, sizeof(bitch_vector_ctx));
	bvctx->bitch_mapa = calloc(((max_nums / (sizeof(bitch_vector) * 8)) + 1),
			sizeof(bitch_vector));
	assert_timeout(bvctx->bitch_mapa);
	return bvctx;
}

static inline bool bitch_checa(bitch_vector_ctx *bvctx,
		entero_largo_sin_signo posicion) {
	entero_largo_sin_signo resultado = 0;
	natural idx_arreglo = 0;
	natural idx_registro = 0;

	idx_arreglo = posicion / 64;
	idx_registro = posicion % 64;

	resultado = bvctx->bitch_mapa[idx_arreglo]
			& (bitch_vector) ((bitch_vector) 1 << idx_registro);

	return !!resultado;
}

static inline void bitch_asigna(bitch_vector_ctx *bvctx,
		entero_largo_sin_signo posicion) {
	natural idx_arreglo = 0;
	natural idx_registro = 0;

	idx_arreglo = posicion / 64;
	idx_registro = posicion % 64;

	bvctx->bitch_mapa[idx_arreglo] |= (bitch_vector) ((bitch_vector) 1
			<< idx_registro);
	bvctx->bitch_numeros_agregados_tam++;

}

static inline void bitch_limpia(bitch_vector_ctx *bvctx,
		entero_largo_sin_signo posicion) {
	int idx_arreglo = 0;
	int idx_registro = 0;
	bitch_vector *bits = bvctx->bitch_mapa;

	idx_arreglo = posicion / 64;
	idx_registro = posicion % 64;

	bits[idx_arreglo] &= (bitch_vector) ~((bitch_vector) 1 << idx_registro);

	bvctx->bitch_numeros_agregados_tam--;
}

static inline void bitch_fini(bitch_vector_ctx *bvctx) {
	free(bvctx->bitch_mapa);
	free(bvctx);
}

#endif

#if 1

#define QUEUE_VALOR_INVALIDO ((void *)LONG_LONG_MAX)

typedef struct Node_t {
	void *datos;
	struct Node_t *prev;
} queue_nodo;

typedef struct queue_t {
	queue_nodo *head;
	queue_nodo *tail;
	int size;
	int limit;
} queue_t;

queue_t *queue_construye(int limit) {
	queue_t *queue = (queue_t*) malloc(sizeof(queue_t));
	if (queue == NULL) {
		return NULL;
	}
	if (limit <= 0) {
		limit = 65535;
	}
	queue->limit = limit;
	queue->size = 0;
	queue->head = NULL;
	queue->tail = NULL;

	return queue;
}

bool queue_vacia(queue_t* pQueue) {
	if (pQueue == NULL) {
		return verdadero;
	}
	if (pQueue->size == 0) {
		return verdadero;
	} else {
		return falso;
	}
}

void *queue_decula(queue_t *pQueue) {
	queue_nodo *item;
	void *mierda;
	if (queue_vacia(pQueue))
		return QUEUE_VALOR_INVALIDO;
	item = pQueue->head;
	mierda = item->datos;
	pQueue->head = (pQueue->head)->prev;
	pQueue->size--;
	free(item);
	return mierda;
}
void queue_destruye(queue_t *queue) {
	while (!queue_vacia(queue)) {
		queue_decula(queue);
	}
	free(queue);
}

bool queue_encula(queue_t *pQueue, void *mierda) {
	queue_nodo *item = (queue_nodo *) calloc(1, sizeof(queue_nodo));
	if ((pQueue == NULL) || (item == NULL)) {
		return falso;
	}
	if (pQueue->size >= pQueue->limit) {
		free(item);
		return falso;
	}
	item->datos = mierda;
	item->prev = NULL;
	if (pQueue->size == 0) {
		pQueue->head = item;
		pQueue->tail = item;

	} else {
		pQueue->tail->prev = item;
		pQueue->tail = item;
	}
	pQueue->size++;
	return verdadero;
}

#endif

typedef struct pcrd {
	union {
		struct {
			int coordenada_y_pcrd;
			int coordenada_x_pcrd;
		} separados_pcrd;
		entero_largo coordenadas_juntas_pcrd;
	} datos_pcrd;
	void *extra;
} pcrd;

#define coord_x datos_pcrd.separados_pcrd.coordenada_x_pcrd
#define coord_y datos_pcrd.separados_pcrd.coordenada_y_pcrd
#define coord_xy datos_pcrd.coordenadas_juntas_pcrd

static inline short pcrd_compacta_a_corto(pcrd *nodo) {
	int coord_xy_compacta = 0;

	coord_xy_compacta = (nodo->coord_x << 8) | nodo->coord_y;

	return coord_xy_compacta;
}

#define pcrd_a_cadena_buffer_local(puto) pcrd_a_cadena((puto),CACA_COMUN_BUF_STATICO)

#if 1
typedef natural hm_iter;
#define HASH_MAP_VALOR_INVALIDO ((hm_iter)CACA_COMUN_VALOR_INVALIDO)
typedef struct hash_map_entry {
	entero_largo llave;
	entero_largo valor;
} hm_entry;
typedef struct hash_map_cubeta {
	uint64_t hash;
	hm_entry *entry;
} hm_cubeta;
typedef struct hmrh {
	hm_cubeta *buckets_;
	uint64_t num_buckets_;
	uint64_t num_buckets_used_;
	uint64_t probing_min_;
	uint64_t probing_max_;
} hm_rr_bs_tabla;
int hmrh_init(hm_rr_bs_tabla *ht, int num_cubetas) {
	ht->num_buckets_ = num_cubetas;
	ht->buckets_ = (hm_cubeta *) calloc(ht->num_buckets_, sizeof(hm_cubeta));
	ht->num_buckets_used_ = 0;
	ht->probing_max_ = num_cubetas;
	return 0;
}
int hmrh_fini(hm_rr_bs_tabla *ht) {
	if (ht->buckets_ != NULL) {
		for (uint32_t i = 0; i < ht->num_buckets_; i++) {
			if (ht->buckets_[i].entry != NULL) {
				free(ht->buckets_[i].entry);
				ht->buckets_[i].entry = NULL;
			}
		}
		free(ht->buckets_);
	}
	return 0;
}
static inline int hmrh_llena_distancia_a_indice_inicio(
		hm_rr_bs_tabla *ht, uint64_t index_stored, uint64_t *distance) {
	hm_cubeta cubeta = ht->buckets_[index_stored];
	*distance = 0;
	if (cubeta.entry == NULL)
		return -1;
	uint64_t num_cubetas = ht->num_buckets_;
	uint64_t index_init = cubeta.hash % num_cubetas;
	if (index_init <= index_stored) {
		*distance = index_stored - index_init;
	} else {
		*distance = index_stored + (num_cubetas - index_init);
	}
	return 0;
}
hm_iter hmrh_obten(hm_rr_bs_tabla *ht,
		const entero_largo key, entero_largo *value) {
	uint64_t num_cubetas = ht->num_buckets_;
	uint64_t prob_max = ht->probing_max_;
	uint64_t hash = key % num_cubetas;
	uint64_t index_init = hash;
	uint64_t probe_distance = 0;
	uint64_t index_current;
	bool found = falso;
	uint32_t i;
	*value = HASH_MAP_VALOR_INVALIDO;
	for (i = 0; i < num_cubetas; i++) {
		index_current = (index_init + i) % num_cubetas;
		hm_entry *entrada = ht->buckets_[index_current].entry;
		if (entrada == NULL) {
			break;
		}
		hmrh_llena_distancia_a_indice_inicio(ht,
				index_current, &probe_distance);
		if (i > probe_distance) {
			break;
		}
		if (entrada->llave == key) {
			*value = entrada->valor;
			found = verdadero;
			break;
		}
	}
	if (found)
		return index_current;
	return HASH_MAP_VALOR_INVALIDO;
}
hm_iter hmrh_pon(hm_rr_bs_tabla *ht, entero_largo key,
		entero_largo value, bool *nuevo_entry) {
	uint64_t num_cubetas = ht->num_buckets_;
	uint64_t prob_max = ht->probing_max_;
	uint64_t prob_min = ht->probing_min_;
	hm_cubeta *cubetas = ht->buckets_;
	*nuevo_entry = verdadero;
	if (ht->num_buckets_used_ == num_cubetas) {
		*nuevo_entry = falso;
		return HASH_MAP_VALOR_INVALIDO;
	}
	ht->num_buckets_used_ += 1;
	uint64_t hash = key % num_cubetas;
	uint64_t index_init = hash;
	hm_entry *entry = (hm_entry *) calloc(1, sizeof(hm_entry));
	entry->llave = key;
	entry->valor = value;
	uint64_t index_current = index_init % num_cubetas;
	uint64_t probe_current = 0;
	uint64_t probe_distance;
	hm_entry *entry_temp;
	uint64_t hash_temp;
	uint64_t i;
	for (i = 0; i < num_cubetas; i++) {
		index_current = (index_init + i) % num_cubetas;
		hm_cubeta *cubeta = cubetas + index_current;
		if (cubeta->entry == NULL) {
			cubeta->entry = entry;
			cubeta->hash = hash;
			if (index_current > prob_max) {
				ht->probing_max_ = index_current;
			}
			if (index_current < prob_min) {
				ht->probing_min_ = index_current;
			}
			break;
		} else {
			if (cubeta->entry->llave == key) {
				free(entry);
				*nuevo_entry = falso;
				break;
			}
			hmrh_llena_distancia_a_indice_inicio(ht,
					index_current, &probe_distance);
			if (probe_current > probe_distance) {
				entry_temp = cubeta->entry;
				hash_temp = cubeta->hash;
				cubeta->entry = entry;
				cubeta->hash = hash;
				entry = entry_temp;
				hash = hash_temp;
				probe_current = probe_distance;
			}
		}
		probe_current++;
	}
	return index_current;
}
int hmrh_borra(hm_rr_bs_tabla *ht,
		const tipo_dato key) {
	uint64_t num_cubetas = ht->num_buckets_;
	uint64_t prob_max = ht->probing_max_;
	uint64_t prob_min = ht->probing_max_;
	uint64_t hash = key % num_cubetas;
	uint64_t index_init = hash;
	bool found = falso;
	uint64_t index_current = 0;
	uint64_t probe_distance = 0;
	hm_entry *entrada = NULL;
	for (uint64_t i = 0; i < num_cubetas; i++) {
		index_current = (index_init + i) % num_cubetas;
		entrada = ht->buckets_[index_current].entry;
		hmrh_llena_distancia_a_indice_inicio(ht,
				index_current, &probe_distance);
		if (entrada == NULL || i > probe_distance) {
			break;
		}
		if (entrada->llave == key) {
			found = verdadero;
			break;
		}
	}
	if (found) {
		free(entrada);
		uint64_t i = 1;
		uint64_t index_previous = 0, index_swap = 0;
		for (i = 1; i < num_cubetas; i++) {
			index_previous = (index_current + i - 1) % num_cubetas;
			index_swap = (index_current + i) % num_cubetas;
			hm_cubeta *cubeta_swap = ht->buckets_ + index_swap;
			hm_cubeta *cubeta_previous = ht->buckets_ + index_previous;
			if (cubeta_swap->entry == NULL) {
				cubeta_previous->entry = NULL;
				break;
			}
			uint64_t distance;
			if (hmrh_llena_distancia_a_indice_inicio(
					ht, index_swap, &distance) != 0) {
				fprintf(stderr, "Error in FillDistanceToInitIndex()");
			}
			if (!distance) {
				cubeta_previous->entry = NULL;
				break;
			}
			cubeta_previous->entry = cubeta_swap->entry;
			cubeta_previous->hash = cubeta_swap->hash;
		}
		if (i < num_cubetas) {
			if (index_previous == prob_min) {
				prob_min++;
				if (prob_min >= num_cubetas) {
					prob_min = 0;
				} else {
					while (prob_min < num_cubetas
							&& ht->buckets_[prob_min].entry) {
						prob_min++;
					}
					if (prob_min >= num_cubetas) {
						prob_min = num_cubetas;
					}
				}
				ht->probing_min_ = prob_min;
			}
			if (index_previous == prob_max) {
				prob_max--;
				if (prob_max >= num_cubetas) {
					prob_max = num_cubetas;
				} else {
					while (((int64_t) prob_max) >= 0
							&& ht->buckets_[prob_max].entry) {
						prob_max--;
					}
					if (prob_max >= num_cubetas) {
						prob_max = 0;
					}
				}
				ht->probing_max_ = prob_max;
			}
		}
		ht->num_buckets_used_--;
		return 0;
	}
	return 1;
}

#endif

#if 1

#define HEAP_SHIT_MAX_NODOS (204|(204<<8))
#define HEAP_SHIT_MAX_LLAVES HV_MAX_LLAVE
#define HEAP_SHIT_VALOR_INVALIDO CACA_COMUN_VALOR_INVALIDO

typedef struct heap_shit_nodo {
	tipo_dato prioridad;
	tipo_dato llave;
	void *valor;
} heap_shit_nodo;

typedef struct heap_shit {
	bool min;
	natural heap_size;
	heap_shit_nodo heap[HEAP_SHIT_MAX_NODOS];
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *tablon_llave_a_idx_heap;
#else
	natural mapa_llave_a_idx_heap[HEAP_SHIT_MAX_NODOS];
#endif
} heap_shit;

static inline heap_shit *heap_shit_init(bool es_min) {
	heap_shit *heap = calloc(1, sizeof(heap_shit));
	assert_timeout(heap);
	heap->heap_size = 0;
	heap->min = es_min;
	memset(heap->heap, HEAP_SHIT_VALOR_INVALIDO, sizeof(heap->heap));
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	heap->tablon_llave_a_idx_heap = calloc(1, sizeof(hm_rr_bs_tabla));
	assert_timeout(heap->tablon_llave_a_idx_heap);
	hmrh_init(heap->tablon_llave_a_idx_heap, HEAP_SHIT_MAX_NODOS);
#else
	for (int i = 0; i < HEAP_SHIT_MAX_NODOS; i++) {
		heap->mapa_llave_a_idx_heap[i] = HEAP_SHIT_VALOR_INVALIDO;
	}
#endif
	return heap;
}

void heap_shit_fini(heap_shit *heap_ctx) {
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hmrh_fini(heap_ctx->tablon_llave_a_idx_heap);
	free(heap_ctx->tablon_llave_a_idx_heap);
#endif
	free(heap_ctx);
}

static inline bool heap_shit_nodo_valido(heap_shit_nodo *nodo) {
	assert_timeout(
			(nodo->llave!=HEAP_SHIT_VALOR_INVALIDO && nodo->prioridad!=HEAP_SHIT_VALOR_INVALIDO) || (nodo->prioridad==nodo->llave));

	return nodo->llave != HEAP_SHIT_VALOR_INVALIDO;
}

static inline natural heap_shit_idx_padre(natural idx_nodo) {
	return idx_nodo >> 1;
}

static inline natural heap_shit_idx_hijo_izq(natural idx_nodo) {
	return idx_nodo << 1;
}

static inline void heap_shit_insert(heap_shit *heap_ctx,
		heap_shit_nodo *nodo_nuevo) {
	natural heap_size = heap_ctx->heap_size;
	heap_shit_nodo *heap = NULL;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *mapeo_inv = heap_ctx->tablon_llave_a_idx_heap;
#else
	natural *mapeo_inv = heap_ctx->mapa_llave_a_idx_heap;
#endif
	bool nuevo;

	heap = heap_ctx->heap;

	heap_size++;
	heap[heap_size] = *nodo_nuevo;
	natural now = heap_size;
	while (heap_shit_nodo_valido(heap + heap_shit_idx_padre(now))
			&& ((heap_ctx->min
					&& heap[heap_shit_idx_padre(now)].prioridad
							> nodo_nuevo->prioridad)
					|| (!heap_ctx->min
							&& heap[heap_shit_idx_padre(now)].prioridad
									< nodo_nuevo->prioridad))) {

		natural idx_padre = heap_shit_idx_padre(now);
		tipo_dato llave_padre = heap[idx_padre].llave;
		assert_timeout(llave_padre!= HEAP_SHIT_VALOR_INVALIDO);

		heap[now] = heap[idx_padre];
#ifdef HEAP_SHIT_MAPEO_COMPLETO
		hmrh_reemplazar(mapeo_inv, llave_padre, now);
#else
		mapeo_inv[llave_padre] = now;
#endif
		now = idx_padre;
	}

	heap[now] = *nodo_nuevo;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hmrh_insertar_nuevo(mapeo_inv, nodo_nuevo->llave,
			now);
#else
	mapeo_inv[nodo_nuevo->llave] = now;
#endif

	heap_ctx->heap_size = heap_size;
}

#define heap_shit_prioridad_en_idx_heap(heap,idx) ((heap)[idx].prioridad)
#define heap_shit_llave_en_idx_heap(heap,idx) ((heap)[idx].llave)

static inline void *heap_shit_delete(heap_shit *heap_ctx, natural idx_a_borrar) {
	natural heap_size = heap_ctx->heap_size;
	natural child, now;
	heap_shit_nodo minElement = { 0 };
	heap_shit_nodo lastElement = { 0 };
	heap_shit_nodo *heap;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *mapeo_inv = heap_ctx->tablon_llave_a_idx_heap;
#else
	natural *mapeo_inv = heap_ctx->mapa_llave_a_idx_heap;
#endif
	void *resultado;
	bool nuevo;

	heap = heap_ctx->heap;

	assert_timeout(heap_size >= idx_a_borrar);
	assert_timeout(idx_a_borrar);

	minElement = heap[idx_a_borrar];
	resultado = minElement.valor;
	lastElement = heap[heap_size--];

	now = idx_a_borrar;
	if (heap_shit_nodo_valido(heap + heap_shit_idx_padre(now))
			&& ((heap_ctx->min
					&& heap[heap_shit_idx_padre(now)].prioridad
							> lastElement.prioridad)
					|| (!heap_ctx->min
							&& (heap[heap_shit_idx_padre(now)].prioridad
									< lastElement.prioridad)))) {
		while (heap_shit_nodo_valido(heap + heap_shit_idx_padre(now))
				&& ((heap_ctx->min
						&& heap[heap_shit_idx_padre(now)].prioridad
								> lastElement.prioridad)
						|| (!heap_ctx->min
								&& (heap[heap_shit_idx_padre(now)].prioridad
										< lastElement.prioridad)))) {
			natural idx_padre = heap_shit_idx_padre(now);
			tipo_dato llave_padre = heap[idx_padre].llave;

			assert_timeout(llave_padre != HEAP_SHIT_VALOR_INVALIDO);

			heap[now] = heap[idx_padre];

#ifdef HEAP_SHIT_MAPEO_COMPLETO
			hmrh_reemplazar(mapeo_inv, llave_padre,
					now);
#else
			mapeo_inv[llave_padre] = now;
#endif

			now = idx_padre;
		}
	} else {

		for (now = idx_a_borrar; heap_shit_idx_hijo_izq(now) <= heap_size; now =
				child) {
			child = heap_shit_idx_hijo_izq(now);
			if (child != heap_size
					&& ((heap_ctx->min
							&& heap[child + 1].prioridad < heap[child].prioridad)
							|| (!heap_ctx->min
									&& heap[child + 1].prioridad
											> heap[child].prioridad))) {
				child++;
			}
			if ((heap_ctx->min && lastElement.prioridad > heap[child].prioridad)
					|| (!heap_ctx->min
							&& lastElement.prioridad < heap[child].prioridad)) {
				heap[now] = heap[child];

#ifdef HEAP_SHIT_MAPEO_COMPLETO
				hmrh_reemplazar(mapeo_inv,
						heap[child].llave, now);
#else
				mapeo_inv[heap_shit_llave_en_idx_heap(heap, child)] = now;
#endif
			} else {
				break;
			}
		}
	}

#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hmrh_borra(mapeo_inv, minElement.llave);
#else
	mapeo_inv[minElement.llave] = HEAP_SHIT_VALOR_INVALIDO;
#endif
	if (heap_size && idx_a_borrar != heap_size + 1) {
		heap[now] = lastElement;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
		hmrh_reemplazar(mapeo_inv, lastElement.llave,
				now);
#else
		mapeo_inv[lastElement.llave] = now;
#endif
	}
	heap_ctx->heap_size = heap_size;
	return resultado;
}

static inline void *heap_shit_borrar_directo(heap_shit *heap_ctx,
		tipo_dato llave) {
	natural heap_size = heap_ctx->heap_size;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *indices_valores = heap_ctx->tablon_llave_a_idx_heap;
#else
	natural *indices_valores = heap_ctx->mapa_llave_a_idx_heap;
#endif
	entero_largo idx_a_borrar;

	assert_timeout(heap_size);

#ifdef HEAP_SHIT_MAPEO_COMPLETO
	natural idx_hm = hmrh_obten(indices_valores,
			llave, &idx_a_borrar);
	assert_timeout(idx_hm!=HASH_MAP_VALOR_INVALIDO);
#else
	idx_a_borrar = indices_valores[llave];
#endif
	assert_timeout(idx_a_borrar != HEAP_SHIT_VALOR_INVALIDO);

	return heap_shit_delete(heap_ctx, idx_a_borrar);
}

static inline void *heap_shit_borra_torpe(heap_shit *heap_ctx) {
	if (heap_ctx->heap_size) {
		return heap_shit_borrar_directo(heap_ctx, heap_ctx->heap[1].llave);
	} else {
		assert_timeout(heap_ctx->heap[1].llave==HEAP_SHIT_VALOR_INVALIDO);
		return NULL;
	}
}

static inline void heap_shit_sube_para_arriba(heap_shit *ctx,
		tipo_dato idx_a_subir
#ifdef HEAP_SHIT_MAPEO_COMPLETO
		, hm_iter idx_en_ht
#endif
		) {
	natural now = idx_a_subir;
	heap_shit_nodo *heap = ctx->heap;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *mapeo_inv = ctx->tablon_llave_a_idx_heap;
#else
	natural *mapeo_inv = ctx->mapa_llave_a_idx_heap;
#endif
	natural idx_padre = heap_shit_idx_padre(now);
	heap_shit_nodo *nodo_a_subir = &(heap_shit_nodo ) { 0 };

	*nodo_a_subir = heap[idx_a_subir];

	/*
	 while (heap_shit_nodo_valido(heap + idx_padre)
	 && ((ctx->min && heap_shit_prioridad_en_idx_heap(heap, idx_padre) > nodo_a_subir->prioridad
	 )
	 || (!ctx->min && ( heap_shit_prioridad_en_idx_heap(heap,
	 idx_padre) < nodo_a_subir->prioridad))))
	 */
	while (idx_padre
			&& heap_shit_prioridad_en_idx_heap(heap, idx_padre)
					> nodo_a_subir->prioridad) {

//		heap_shit_intercambia_nodos(ctx, idx_padre, now);

#ifdef HEAP_SHIT_MAPEO_COMPLETO
		hmrh_reemplazar(mapeo_inv,
				heap_shit_llave_en_idx_heap(heap, idx_padre), now);
#else
		mapeo_inv[heap_shit_llave_en_idx_heap(heap, idx_padre)] = now;
#endif
		heap[now] = heap[idx_padre];

		now = idx_padre;
		idx_padre = heap_shit_idx_padre(now);
	}

#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hmrh_indice_pon_valor(mapeo_inv, idx_en_ht, now);
#else
	mapeo_inv[nodo_a_subir->llave] = now;
#endif
	heap[now] = *nodo_a_subir;
}

static inline void heap_shit_altera_prioridad(heap_shit *ctx, tipo_dato llave,
		tipo_dato prioridad_nueva) {

	natural heap_size = ctx->heap_size;
#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_rr_bs_tabla *indices_valores = ctx->tablon_llave_a_idx_heap;
#else
	natural *indices_valores = ctx->mapa_llave_a_idx_heap;
#endif
	heap_shit_nodo *heap = ctx->heap;
	entero_largo idx_a_subir;
	heap_shit_nodo *minElement;

	assert_timeout(heap_size);

#ifdef HEAP_SHIT_MAPEO_COMPLETO
	hm_iter idx_hm = hmrh_obten(indices_valores,
			llave, &idx_a_subir);
	assert_timeout(idx_hm!=HASH_MAP_VALOR_INVALIDO);
#else
	idx_a_subir = indices_valores[llave];
#endif
	assert_timeout(idx_a_subir != HEAP_SHIT_VALOR_INVALIDO);

	minElement = heap + idx_a_subir;
	minElement->prioridad = prioridad_nueva;

	heap_shit_sube_para_arriba(ctx, idx_a_subir
#ifdef HEAP_SHIT_MAPEO_COMPLETO
			, idx_hm
#endif
			);
}

#endif

#define HV_VALOR_INVALIDO (CACA_COMUN_VALOR_INVALIDO-10)
#define HV_INVIABLE (HV_VALOR_INVALIDO-101)

typedef enum huaronverga_caso_familiar {
	vertical_huaronverga_caso_familiar = 0,
	horizontal_huaronverga_caso_familiar,
	esq_1_huaronverga_caso_familiar,
	esq_2_huaronverga_caso_familiar,
	esq_3_huaronverga_caso_familiar,
	esq_4_huaronverga_caso_familiar,
	final_huaronverga_caso_familiar,
	invalido_huaronverga_caso_familiar = HV_VALOR_INVALIDO
} huaronverga_caso_familiar;
#define inicial_huaronverga_caso_familiar vertical_huaronverga_caso_familiar

typedef enum huaronverga_movimientos_decendiente_directo_idx {
	arriba_huaronverga_movimientos_decendiente_directo_idx = 0,
	derecha_huaronverga_movimientos_decendiente_directo_idx,
	abajo_huaronverga_movimientos_decendiente_directo_idx,
	izquierda_huaronverga_movimientos_decendiente_directo_idx,
	ultimo_huaronverga_movimientos_decendiente_directo_idx,
	invalido_huaronverga_movimientos_decendiente_directo_idx = HV_VALOR_INVALIDO
} huaronverga_movimientos_decendiente_directo_idx;
#define primero_huaronverga_movimientos_decendiente_directo_idx arriba_huaronverga_movimientos_decendiente_directo_idx

#define HV_MAX_FILAS 200
#define HV_MAX_COLUMNAS 200
#define HV_MAX_ELEMENTOS (HV_MAX_FILAS*HV_MAX_COLUMNAS)
#define HV_MAX_ELEMENTOS_RODEADOS ((HV_MAX_FILAS+4)*(HV_MAX_COLUMNAS+4))
#define HV_CARACTER_BLOQUE_LIBRE '1'
#define HV_CARACTER_BLOQUE_BLOKEADO '0'

typedef struct huaronverga_ctx {
	byteme matrix[HV_MAX_FILAS][HV_MAX_COLUMNAS];
	byteme matrix_rodeada[HV_MAX_FILAS + 4][HV_MAX_COLUMNAS
			+ 4];
	tipo_dato matrix_chosto_brinco[final_huaronverga_caso_familiar][HV_MAX_FILAS][HV_MAX_COLUMNAS];
	tipo_dato matrix_chosto_minimo[HV_MAX_FILAS][HV_MAX_COLUMNAS];
	pcrd matrix_predecesores[HV_MAX_FILAS][HV_MAX_COLUMNAS];
	tipo_dato chosto_brinco;
	natural columnas_tam;
	natural filas_tam;
} huaronverga_ctx;

typedef struct huaronverga_args {
	pcrd *abuelo;
	pcrd *padre;
	pcrd *hijo;
	pcrd *mas_arriba;
	pcrd *mas_abajo;
	tipo_dato chosto_act_hijo;
	huaronverga_caso_familiar cacaso;
} huaronverga_args;

pcrd movimientos_decendiente_directo[] = { { 0, 1 }, { 1, 0 },
		{ 0, -1 }, { -1, 0 } };

pcrd movimientos_posible_abuelo[][2] = {
		[vertical_huaronverga_caso_familiar]= { { 1, 0 }, { -1, 0 } },
		[horizontal_huaronverga_caso_familiar ]= { { 0, 1 }, { 0, -1 } },
		[esq_1_huaronverga_caso_familiar ... final_huaronverga_caso_familiar
				]= { {
				HV_VALOR_INVALIDO,
				HV_VALOR_INVALIDO }, {
				HV_VALOR_INVALIDO,
				HV_VALOR_INVALIDO } } };
natural movimientos_posible_abuelo_tam[] = { [vertical_huaronverga_caso_familiar
		]= 2, [horizontal_huaronverga_caso_familiar ]=2,
		[esq_1_huaronverga_caso_familiar ... final_huaronverga_caso_familiar
				]= 0 };

huaronverga_caso_familiar cacasos_abuelo_hijo[][ultimo_huaronverga_movimientos_decendiente_directo_idx] =
		{
// hijo:	ARRIBA								DERECHA								ABAJO								IZQUIERDA
				{ invalido_huaronverga_caso_familiar,
						esq_4_huaronverga_caso_familiar,
						vertical_huaronverga_caso_familiar,
						esq_3_huaronverga_caso_familiar }, // abuelo: ARRIBA
				{ esq_4_huaronverga_caso_familiar,
						invalido_huaronverga_caso_familiar,
						esq_1_huaronverga_caso_familiar,
						horizontal_huaronverga_caso_familiar }, // abuelo: DERECHA
				{ vertical_huaronverga_caso_familiar,
						esq_1_huaronverga_caso_familiar,
						invalido_huaronverga_caso_familiar,
						esq_2_huaronverga_caso_familiar }, // abuelo: ABAJO
				{ esq_3_huaronverga_caso_familiar,
						horizontal_huaronverga_caso_familiar,
						esq_2_huaronverga_caso_familiar,
						invalido_huaronverga_caso_familiar } // abuelo: IZQUIERDA
		};

static inline tipo_dato huaronverga_cc(pcrd *nodo) {
	tipo_dato coord_xy_compacta = 0;

	coord_xy_compacta = pcrd_compacta_a_corto(nodo)
			& ((tipo_dato) 0xffff);

	assert_timeout(coord_xy_compacta<=HEAP_SHIT_MAX_LLAVES);

	return coord_xy_compacta;
}

static inline tipo_dato huaronverga_cc_rodeada(
		pcrd *nodo) {
	tipo_dato coord_xy_compacta = 0;

	coord_xy_compacta = pcrd_compacta_a_corto(nodo)
			& ((tipo_dato) 0xffff);

	assert_timeout(coord_xy_compacta <= HV_MAX_LLAVE_RODEADA);

	return coord_xy_compacta;
}

static inline huaronverga_caso_familiar huaronverga_obten_caso_familiar(
		huaronverga_args *hvargs) {
	pcrd *abuelo = hvargs->abuelo;
	pcrd *padre = hvargs->padre;
	pcrd *hijo = hvargs->hijo;
	huaronverga_caso_familiar cacaso = invalido_huaronverga_caso_familiar;
	huaronverga_movimientos_decendiente_directo_idx caso_abuelo_idx =
			invalido_huaronverga_movimientos_decendiente_directo_idx;
	huaronverga_movimientos_decendiente_directo_idx caso_hijo_idx =
			invalido_huaronverga_movimientos_decendiente_directo_idx;

	for (caso_abuelo_idx =
	primero_huaronverga_movimientos_decendiente_directo_idx;
			caso_abuelo_idx
					< ultimo_huaronverga_movimientos_decendiente_directo_idx;
			caso_abuelo_idx++) {

		pcrd *movimiento_act = movimientos_decendiente_directo
				+ caso_abuelo_idx;

		pcrd *potencial_abuelo = &(pcrd )
				{ .coord_x = padre->coord_x + movimiento_act->coord_x,
						.coord_y =
						padre->coord_y + movimiento_act->coord_y };
		if (potencial_abuelo->coord_xy == abuelo->coord_xy) {
			break;
		}

	}
	assert_timeout(
			caso_abuelo_idx
					!= invalido_huaronverga_movimientos_decendiente_directo_idx);

	for (caso_hijo_idx =
	primero_huaronverga_movimientos_decendiente_directo_idx;
			caso_hijo_idx
					< ultimo_huaronverga_movimientos_decendiente_directo_idx;
			caso_hijo_idx++) {

		pcrd *movimiento_act = movimientos_decendiente_directo
				+ caso_hijo_idx;

		pcrd *potencial_hijo = &(pcrd )
				{ .coord_x = padre->coord_x + movimiento_act->coord_x,
						.coord_y =
						padre->coord_y + movimiento_act->coord_y };
		if (potencial_hijo->coord_xy == hijo->coord_xy) {
			break;
		}

	}

	assert_timeout(
			caso_hijo_idx
					!= invalido_huaronverga_movimientos_decendiente_directo_idx);

	cacaso = cacasos_abuelo_hijo[caso_abuelo_idx][caso_hijo_idx];

	assert_timeout(caso_hijo_idx != invalido_huaronverga_caso_familiar);

	hvargs->cacaso = cacaso;
	return cacaso;
}

static inline void huaronverga_genera_vecino_en_idx(pcrd *origen,
		pcrd *vecino,
		huaronverga_movimientos_decendiente_directo_idx idx) {
	pcrd *mov_act = movimientos_decendiente_directo + idx;
	vecino->coord_x = origen->coord_x + mov_act->coord_x;
	vecino->coord_y = origen->coord_y + mov_act->coord_y;
}

#define huaronverga_obten_valor_en_coord(matrix,puto) (matrix)[puto->coord_x][puto->coord_y]

#define huaronverga_genera_puto_rodeado_local(nodo) (&(pcrd ){.coord_x=(nodo)->coord_x+2,.coord_y=(nodo)->coord_y+2})
#define huaronverga_genera_puto_desrodeado_local(nodo) (&(pcrd ){.coord_x=(nodo)->coord_x-2,.coord_y=(nodo)->coord_y-2})

static inline bool huaronverga_va_pcrd(huaronverga_ctx *ctx,
		pcrd *puto) {
	bool valido = verdadero;
	if (puto->coord_x == HV_VALOR_INVALIDO
			|| puto->coord_y == HV_VALOR_INVALIDO || puto->coord_x < 0
			|| puto->coord_y < 0 || puto->coord_x >= ctx->filas_tam
			|| puto->coord_y >= ctx->columnas_tam) {
		valido = falso;
	}
	return valido;
}

static inline bool huaronverga_va_pcrd_rodeado(
		huaronverga_ctx *ctx, pcrd *puto) {
	bool valido = verdadero;
	if (puto->coord_x == HV_VALOR_INVALIDO
			|| puto->coord_y == HV_VALOR_INVALIDO || puto->coord_x < 0
			|| puto->coord_y < 0 || puto->coord_x >= ctx->filas_tam + 4
			|| puto->coord_y >= ctx->columnas_tam + 4) {
		valido = falso;
	}
	return valido;
}

static inline bool huaronverga_va_pcrd_valor_matrix(
		huaronverga_ctx *ctx, pcrd *puto) {
	bool valido = verdadero;
	if (!huaronverga_va_pcrd(ctx, puto) ||
	huaronverga_obten_valor_en_coord(ctx->matrix,puto)!=HV_CARACTER_BLOQUE_LIBRE
	) {
		valido = falso;
	}
	return valido;
}

static inline bool huaronverga_va_pcrd_valor_matrix_rodeada(
		huaronverga_ctx *ctx, pcrd *puto) {
	bool valido = verdadero;
	if (!huaronverga_va_pcrd_rodeado(ctx, puto) ||
	huaronverga_obten_valor_en_coord(ctx->matrix_rodeada,puto)!=HV_CARACTER_BLOQUE_LIBRE
	) {
		valido = falso;
	}
	return valido;
}

static inline natural huaronverga_genera_vecinos_validos(huaronverga_ctx *ctx,
		pcrd *caca, pcrd *vecinos, bool solo_validos) {
	natural vecinos_cnt = 0;

	for (huaronverga_movimientos_decendiente_directo_idx i =
	primero_huaronverga_movimientos_decendiente_directo_idx;
			i < ultimo_huaronverga_movimientos_decendiente_directo_idx; i++) {
		pcrd *vecino_act = vecinos + vecinos_cnt;
		pcrd *vecino_act_rodeado = NULL;

		huaronverga_genera_vecino_en_idx(caca, vecino_act, i);
		vecino_act_rodeado = huaronverga_genera_puto_rodeado_local(vecino_act);

		if (huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
				vecino_act_rodeado) || !solo_validos) {
			vecinos_cnt++;
		}
	}
	return vecinos_cnt;
}

static inline void huaronverga_pon_valor_en_coord_stack_byteme(
		byteme matrix[HV_MAX_FILAS + 4][HV_MAX_COLUMNAS + 4],
		pcrd *puto, byteme valor) {
	matrix[puto->coord_x][puto->coord_y] = valor;
}

static inline void huaronverga_pon_valor_en_coord_stack_pcrd(
		pcrd matrix[HV_MAX_FILAS][HV_MAX_COLUMNAS],
		pcrd *puto, pcrd *valor) {
	matrix[puto->coord_x][puto->coord_y] = *valor;
}

static inline void huaronverga_pon_valor_en_coord_stack_natural(
		natural matrix[HV_MAX_FILAS][HV_MAX_COLUMNAS],
		pcrd *puto, natural valor) {
	matrix[puto->coord_x][puto->coord_y] = valor;
}

typedef struct huaronverga_chosto_bfs_elem {
	pcrd puto;
	natural chosto;
} huaronverga_chosto_bfs_elem;

huaronverga_chosto_bfs_elem chostos_queue_elems[HV_MAX_ELEMENTOS_RODEADOS
		+ 1] = { HV_VALOR_INVALIDO };

natural chostos_bfs[HV_MAX_LLAVE_RODEADA + 1] = {
HV_VALOR_INVALIDO };

static inline tipo_dato huaronverga_chosto_por_busqueda_en_amplitud(
		huaronverga_ctx *ctx,
		byteme matrix[HV_MAX_FILAS + 4][HV_MAX_COLUMNAS + 4],
		pcrd *inicio, pcrd *fin,
		huaronverga_chosto_bfs_elem *chostos_queue_elems, natural *chostos,
		bitch_vector_ctx *bitch_map) {
	tipo_dato chosto = 0;
	queue_t *kha = NULL;
	bool se_encontro_fin = falso;
	natural putos_tmp_cnt = 0;
	bitch_vector_ctx *bvctx = NULL;
	pcrd *inicio_rodeado = huaronverga_genera_puto_rodeado_local(
			inicio);
	pcrd *fin_rodeado = huaronverga_genera_puto_rodeado_local(fin);
	bool todos_encontrados = falso;

	if (inicio->coord_xy == fin->coord_xy) {
		return 0;
	}

	if (!huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
			inicio_rodeado)
			|| !huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
					fin_rodeado)) {
		return HV_VALOR_INVALIDO;
	}

	bvctx = bitch_init(HV_MAX_LLAVE_RODEADA);

	kha = queue_construye(HV_MAX_FILAS * HV_MAX_COLUMNAS);

	huaronverga_chosto_bfs_elem *elem_inicial = chostos_queue_elems
			+ putos_tmp_cnt++;
	elem_inicial->puto = *inicio_rodeado;
	elem_inicial->chosto = 0;
	queue_encula(kha, elem_inicial);

	chostos[huaronverga_cc_rodeada(inicio_rodeado)] = 0;
	chostos[huaronverga_cc_rodeada(fin_rodeado)] =
	HV_VALOR_INVALIDO;

	while (!queue_vacia(kha)) {
		huaronverga_chosto_bfs_elem *act_elem = queue_decula(kha);
		pcrd *act = &act_elem->puto;
		if (act_elem->chosto >= ctx->chosto_brinco) {
			break;
		}

		for (huaronverga_movimientos_decendiente_directo_idx vecino_idx = 0;
				vecino_idx
						< ultimo_huaronverga_movimientos_decendiente_directo_idx;
				vecino_idx++) {
			huaronverga_chosto_bfs_elem *vecino_elem = chostos_queue_elems
					+ putos_tmp_cnt;
			pcrd *vecino = &vecino_elem->puto;
			tipo_dato vecino_compacto = 0;

			huaronverga_genera_vecino_en_idx(act, vecino, vecino_idx);

			vecino_compacto = huaronverga_cc_rodeada(vecino);

			if (huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
					vecino) && !bitch_checa(bvctx, vecino_compacto)) {

				putos_tmp_cnt++;
				vecino_elem->chosto = act_elem->chosto + 1;
				queue_encula(kha, vecino_elem);
				chostos[vecino_compacto] = vecino_elem->chosto;
				bitch_asigna(bvctx, vecino_compacto);
				if (vecino->coord_xy == fin_rodeado->coord_xy) {
					se_encontro_fin = verdadero;
				}
				if (bitch_map && bitch_checa(bitch_map, vecino_compacto)) {
					bitch_limpia(bitch_map, vecino_compacto);
				}
				if (bitch_map && !bitch_map->bitch_numeros_agregados_tam) {
					todos_encontrados = verdadero;
					break;
				}
			}
		}
		if (todos_encontrados) {
			break;
		}
	}

	if (se_encontro_fin) {
		chosto = chostos[huaronverga_cc_rodeada(fin_rodeado)];
	} else {
		chosto = ctx->chosto_brinco;
	}

	queue_destruye(kha);
	bitch_fini(bvctx);

	if (chosto > ctx->chosto_brinco) {
		chosto = ctx->chosto_brinco;
	}

	return chosto;
}

static inline tipo_dato huaronverga_chosto_por_busqueda_en_amplitud_brincando(
		huaronverga_ctx *ctx,
		byteme matrix[HV_MAX_FILAS + 4][HV_MAX_COLUMNAS + 4],
		pcrd *inicio, pcrd *invalido, pcrd *fin,
		huaronverga_chosto_bfs_elem *chostos_queue_elems, natural *chostos,
		bitch_vector_ctx *bitch_map) {

	tipo_dato chosto = 0;
	byteme valor_ant = 0;
	pcrd *invalido_rodeado = huaronverga_genera_puto_rodeado_local(
			invalido);
	pcrd *inicio_rodeado = huaronverga_genera_puto_rodeado_local(
			inicio);

	valor_ant = huaronverga_obten_valor_en_coord(matrix, invalido_rodeado);
	huaronverga_pon_valor_en_coord_stack_byteme(matrix, invalido_rodeado,
	HV_CARACTER_BLOQUE_BLOKEADO);

	chosto = huaronverga_chosto_por_busqueda_en_amplitud(ctx, matrix, inicio,
			fin, chostos_queue_elems, chostos, bitch_map);

	huaronverga_pon_valor_en_coord_stack_byteme(matrix, invalido_rodeado,
			valor_ant);

	return chosto;
}

static inline tipo_dato huaronverga_calcula_chosto_brinco(huaronverga_ctx *ctx,
		huaronverga_args *hvargs) {
	tipo_dato res = 0;
	pcrd *abuelo = hvargs->abuelo;
	pcrd *padre = hvargs->padre;
	pcrd *hijo = hvargs->hijo;
	pcrd *mas_abajo = &(pcrd ) { 0 };
	pcrd *mas_arriba = &(pcrd ) { 0 };
	pcrd vecinos[4] = { 0 };
	natural vecinos_cnt = 0;
	pcrd *padre_rodeado = huaronverga_genera_puto_rodeado_local(padre);
	pcrd *mas_abajo_rodeado = NULL;
	tipo_dato (*matrix_chosto_brinco)[final_huaronverga_caso_familiar][HV_MAX_FILAS][HV_MAX_COLUMNAS] =
			&ctx->matrix_chosto_brinco;
	huaronverga_caso_familiar cacaso = hvargs->cacaso;
	bitch_vector_ctx *bitch_map = bitch_init(HV_MAX_LLAVE_RODEADA);

	assert_timeout(abuelo->coord_xy!=padre->coord_xy);
	assert_timeout(padre->coord_xy!=hijo->coord_xy);
	assert_timeout(hijo->coord_xy!=abuelo->coord_xy);

	*mas_abajo = *hvargs->mas_abajo;
	*mas_arriba = *hvargs->mas_arriba;

	mas_abajo_rodeado = huaronverga_genera_puto_rodeado_local(mas_abajo);

	vecinos_cnt = huaronverga_genera_vecinos_validos(ctx, padre_rodeado,
			vecinos, falso);

	int i = 0;
	for (i = 0; i < vecinos_cnt; i++) {
		pcrd *vecino_act = vecinos + i;
		tipo_dato chosto_act = HV_VALOR_INVALIDO;
		tipo_dato coord_compacta = 0;

		coord_compacta = huaronverga_cc_rodeada(vecino_act);

		if (huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
				vecino_act) && vecino_act->coord_xy == padre_rodeado->coord_xy) {
			chosto_act = 0;
		} else {
			chosto_act = HV_VALOR_INVALIDO;
		}
		chostos_bfs[coord_compacta] = chosto_act;
		bitch_asigna(bitch_map, coord_compacta);
	}

	res = huaronverga_chosto_por_busqueda_en_amplitud_brincando(ctx,
			ctx->matrix_rodeada, mas_abajo, padre, mas_arriba,
			chostos_queue_elems, chostos_bfs, bitch_map);

	bitch_fini(bitch_map);

	for (huaronverga_movimientos_decendiente_directo_idx i =
	primero_huaronverga_movimientos_decendiente_directo_idx, vecinos_cnt = 0;
			i < ultimo_huaronverga_movimientos_decendiente_directo_idx;
			i++, vecinos_cnt++) {
		pcrd *vecino_act = vecinos + vecinos_cnt;
		if (huaronverga_va_pcrd_valor_matrix_rodeada(ctx,
				vecino_act)) {
			pcrd *mas_abajo_act = NULL;
			tipo_dato chosto_act = 0;

			huaronverga_caso_familiar cacaso_act =
					invalido_huaronverga_caso_familiar;

			chosto_act = chostos_bfs[huaronverga_cc_rodeada(
					vecino_act)];

			switch (cacaso) {
			case esq_1_huaronverga_caso_familiar:
			case esq_2_huaronverga_caso_familiar:
			case vertical_huaronverga_caso_familiar:
				mas_abajo_act = mas_abajo;
				switch (i) {
				case arriba_huaronverga_movimientos_decendiente_directo_idx:
					cacaso_act = vertical_huaronverga_caso_familiar;
					break;
				case izquierda_huaronverga_movimientos_decendiente_directo_idx:
					cacaso_act = esq_2_huaronverga_caso_familiar;
					break;
				case abajo_huaronverga_movimientos_decendiente_directo_idx:
					assert_timeout(
							mas_abajo->coord_xy==huaronverga_genera_puto_desrodeado_local(vecino_act)->coord_xy)
					;
					break;
				case derecha_huaronverga_movimientos_decendiente_directo_idx:
					cacaso_act = esq_1_huaronverga_caso_familiar;
					break;
				default:
					abort();
					break;
				}
				break;
			case esq_3_huaronverga_caso_familiar:
			case horizontal_huaronverga_caso_familiar:
				switch (i) {
				case arriba_huaronverga_movimientos_decendiente_directo_idx:
					mas_abajo_act = mas_abajo;
					cacaso_act = esq_3_huaronverga_caso_familiar;
					break;
				case izquierda_huaronverga_movimientos_decendiente_directo_idx:
					assert_timeout(
							mas_abajo->coord_xy==huaronverga_genera_puto_desrodeado_local(vecino_act)->coord_xy)
					;
					break;
				case abajo_huaronverga_movimientos_decendiente_directo_idx:
					mas_abajo_act = huaronverga_genera_puto_desrodeado_local(
							vecino_act);
					cacaso_act = esq_2_huaronverga_caso_familiar;
					break;
				case derecha_huaronverga_movimientos_decendiente_directo_idx:
					break;
				default:
					abort();
					break;
				}
				break;
			case esq_4_huaronverga_caso_familiar:
				switch (i) {
				case arriba_huaronverga_movimientos_decendiente_directo_idx:
					mas_abajo_act = mas_abajo;
					cacaso_act = cacaso;
					break;
				case izquierda_huaronverga_movimientos_decendiente_directo_idx:
					mas_abajo_act = huaronverga_genera_puto_desrodeado_local(
							vecino_act);
					cacaso_act = horizontal_huaronverga_caso_familiar;
					break;
				case abajo_huaronverga_movimientos_decendiente_directo_idx:
					mas_abajo_act = huaronverga_genera_puto_desrodeado_local(
							vecino_act);
					cacaso_act = esq_1_huaronverga_caso_familiar;
					break;
				case derecha_huaronverga_movimientos_decendiente_directo_idx:
					assert_timeout(
							mas_abajo->coord_xy==huaronverga_genera_puto_desrodeado_local(vecino_act)->coord_xy)
					;
					break;
				default:
					abort();
					break;
				}
				break;
			default:
				abort();
				break;
			}

			if (cacaso_act != invalido_huaronverga_caso_familiar) {
				if (chosto_act == HV_VALOR_INVALIDO
						|| chosto_act > ctx->chosto_brinco) {
					chosto_act = ctx->chosto_brinco;
				}
				(*matrix_chosto_brinco)[cacaso_act][mas_abajo_act->coord_x][mas_abajo_act->coord_y] =
						chosto_act;
			}
		}
	}

	return res;
}

static inline tipo_dato huaronverga_obten_chosto_brinco(huaronverga_ctx *ctx,
		huaronverga_args *hvargs) {
	huaronverga_caso_familiar cacaso = invalido_huaronverga_caso_familiar;
	pcrd *abuelo = hvargs->abuelo;
	pcrd *padre = hvargs->padre;
	pcrd *hijo = hvargs->hijo;
	pcrd *mas_abajo = NULL;
	pcrd *mas_arriba = NULL;
	tipo_dato res = 0;

	assert_timeout(abuelo->coord_xy!=padre->coord_xy);
	assert_timeout(padre->coord_xy!=hijo->coord_xy);
	assert_timeout(hijo->coord_xy!=abuelo->coord_xy);

	cacaso = huaronverga_obten_caso_familiar(hvargs);
	hvargs->cacaso = cacaso;

	mas_abajo = abuelo->coord_xy < hijo->coord_xy ? abuelo : hijo;
	mas_arriba = abuelo->coord_xy > hijo->coord_xy ? abuelo : hijo;
	hvargs->mas_abajo = mas_abajo;
	hvargs->mas_arriba = mas_arriba;

	res =
			ctx->matrix_chosto_brinco[cacaso][mas_abajo->coord_x][mas_abajo->coord_y];

	if (res == HV_VALOR_INVALIDO) {
		res = huaronverga_calcula_chosto_brinco(ctx, hvargs);
		ctx->matrix_chosto_brinco[cacaso][mas_abajo->coord_x][mas_abajo->coord_y] =
				res;
	}

	return res;
}

static inline tipo_dato huaronverga_mejora_chosto_hijo(huaronverga_ctx *ctx,
		huaronverga_args *hvargs) {
	tipo_dato chosto = hvargs->chosto_act_hijo;
	huaronverga_caso_familiar cacaso = hvargs->cacaso;
	pcrd *abuelo = hvargs->abuelo;
	pcrd *padre = hvargs->padre;
	pcrd *hijo = hvargs->hijo;

	for (int i = 0; i < movimientos_posible_abuelo_tam[cacaso]; i++) {
		tipo_dato chosto_posible_bisabuelo_padre = 0;
		tipo_dato chosto_posible_abuelo_hijo = 0;
		tipo_dato chosto_posible_abuelo = 0;
		tipo_dato chosto_hijo = 0;
		pcrd *mov_act = &movimientos_posible_abuelo[cacaso][i];
		pcrd *posible_abuelo = &(pcrd ) { .coord_x =
				padre->coord_x + mov_act->coord_x, .coord_y =
				padre->coord_y + mov_act->coord_y };

		assert_timeout(posible_abuelo->coord_x!=HV_VALOR_INVALIDO);
		assert_timeout(posible_abuelo->coord_y!=HV_VALOR_INVALIDO);

		if (!huaronverga_va_pcrd_valor_matrix(ctx,
				posible_abuelo)) {
			continue;
		}

		chosto_posible_abuelo = huaronverga_obten_valor_en_coord(
				ctx->matrix_chosto_minimo, posible_abuelo);

		if (chosto_posible_abuelo == HV_VALOR_INVALIDO) {
			continue;
		}

		pcrd *posible_bisabuelo = &huaronverga_obten_valor_en_coord(
				ctx->matrix_predecesores, posible_abuelo);

		if (huaronverga_va_pcrd_valor_matrix(ctx,
				posible_bisabuelo) && posible_bisabuelo->coord_xy != padre->coord_xy) {
			assert_timeout(
					posible_bisabuelo->coord_y!=HV_VALOR_INVALIDO);

			chosto_posible_bisabuelo_padre = huaronverga_obten_chosto_brinco(
					ctx, &(huaronverga_args ) { .cacaso = cacaso, .abuelo =
									posible_bisabuelo, .padre = posible_abuelo,
									.hijo = padre });
			assert_timeout(
					chosto_posible_bisabuelo_padre!=HV_VALOR_INVALIDO);

			chosto_posible_bisabuelo_padre++;
		}

		chosto_posible_abuelo_hijo = huaronverga_obten_chosto_brinco(ctx,
				&(huaronverga_args ) { .cacaso = cacaso, .abuelo =
								posible_abuelo, .padre = padre, .hijo = hijo });

		assert_timeout(chosto_posible_abuelo_hijo!=HV_VALOR_INVALIDO);
		chosto_posible_abuelo_hijo++;

		chosto_hijo = chosto_posible_abuelo + chosto_posible_bisabuelo_padre
				+ chosto_posible_abuelo_hijo;

		if (chosto_hijo < chosto) {
			chosto = chosto_hijo;
		}
	}

	return chosto;
}

static inline tipo_dato huaronverga_dickstra(huaronverga_ctx *ctx,
		pcrd *cacao, pcrd *vacio, pcrd *salida) {
	pcrd (*matrix_predecesores)[HV_MAX_FILAS][HV_MAX_COLUMNAS] =
			&ctx->matrix_predecesores;
	tipo_dato (*matrix_chosto_minimo)[HV_MAX_FILAS][HV_MAX_COLUMNAS] =
			&ctx->matrix_chosto_minimo;
	pcrd vecinos_tmp[ultimo_huaronverga_movimientos_decendiente_directo_idx] =
			{ 0 };
	natural vecinos_tmp_cnt = 0;
	bool encontrada_salida = falso;
	tipo_dato chosto_final = HV_VALOR_INVALIDO;

	pcrd *putos_tmp = NULL;
	natural putos_tmp_cnt = 0;

	heap_shit *cola_prioridad = NULL;

	bitch_vector_ctx *bvctx = NULL;

	if (cacao->coord_xy == salida->coord_xy) {
		return 0;
	}

	if (!huaronverga_va_pcrd_valor_matrix(ctx, cacao)
			|| !huaronverga_va_pcrd_valor_matrix(ctx, vacio)
			|| !huaronverga_va_pcrd_valor_matrix(ctx, salida)) {
		return HV_VALOR_INVALIDO;
	}

	putos_tmp = calloc(HV_MAX_ELEMENTOS << 1, sizeof(putos_tmp));
	assert_timeout(putos_tmp);

	bvctx = bitch_init(HV_MAX_LLAVE);

	cola_prioridad = heap_shit_init(verdadero);

	for (int i = 0; i < ctx->filas_tam; i++) {
		for (int j = 0; j < ctx->columnas_tam; j++) {
			pcrd *puto_act = putos_tmp + putos_tmp_cnt++;
			puto_act->coord_y = j;
			puto_act->coord_x = i;
			if (huaronverga_obten_valor_en_coord(ctx->matrix,puto_act)==HV_CARACTER_BLOQUE_LIBRE && huaronverga_cc(puto_act)!=huaronverga_cc(cacao)) {
				heap_shit_insert(cola_prioridad, &(heap_shit_nodo ) {.prioridad =
					HV_VALOR_INVALIDO, .llave =
					huaronverga_cc(puto_act), .valor =
					puto_act});
			}
		}
	}

	bitch_asigna(bvctx, huaronverga_cc(cacao));
	huaronverga_pon_valor_en_coord_stack_natural(*matrix_chosto_minimo, cacao,
			0);

	vecinos_tmp_cnt = huaronverga_genera_vecinos_validos(ctx, cacao,
			vecinos_tmp, verdadero);

	for (int i = 0; i < vecinos_tmp_cnt; i++) {
		natural chosto_vacio_primer_mov = 0;
		pcrd *vecino_act = vecinos_tmp + i;

		if (cacao->coord_xy != vacio->coord_xy) {
			chosto_vacio_primer_mov =
					huaronverga_chosto_por_busqueda_en_amplitud_brincando(ctx,
							ctx->matrix_rodeada, vacio, cacao, vecino_act,
							chostos_queue_elems, chostos_bfs, NULL) + 1;
		} else {
			chosto_vacio_primer_mov = 2;
		}

		vecino_act = heap_shit_borrar_directo(cola_prioridad,
				huaronverga_cc(vecino_act));

		heap_shit_insert(cola_prioridad, &(heap_shit_nodo ) { .prioridad =
						chosto_vacio_primer_mov, .llave =
						huaronverga_cc(vecino_act), .valor =
						vecino_act });
		huaronverga_pon_valor_en_coord_stack_pcrd(*matrix_predecesores,
				vecino_act, cacao);
		huaronverga_pon_valor_en_coord_stack_natural(*matrix_chosto_minimo,
				vecino_act, chosto_vacio_primer_mov);
	}

	while (cola_prioridad->heap_size) {
		pcrd *padre = heap_shit_borra_torpe(cola_prioridad);
		assert_timeout(padre);
		tipo_dato chosto_padre = huaronverga_obten_valor_en_coord(
				*matrix_chosto_minimo, padre);

		if (padre->coord_xy == salida->coord_xy) {
			encontrada_salida = verdadero;
			break;
		}
		if (chosto_padre == HV_VALOR_INVALIDO) {
			break;
		}

		bitch_asigna(bvctx, huaronverga_cc(padre));

		pcrd *abuelo = &huaronverga_obten_valor_en_coord(
				*matrix_predecesores, padre);
		assert_timeout(abuelo);
		vecinos_tmp_cnt = huaronverga_genera_vecinos_validos(ctx, padre,
				vecinos_tmp, verdadero);

		for (int i = 0; i < vecinos_tmp_cnt; i++) {
			tipo_dato chosto_act = 0;
			pcrd *hijo = &(pcrd ) { 0 };
			*hijo = vecinos_tmp[i];

			if (bitch_checa(bvctx, huaronverga_cc(hijo))) {
				continue;
			}

			huaronverga_args *hvargs = &(huaronverga_args ) { .abuelo = abuelo,
							.padre = padre, .hijo = hijo };
			tipo_dato chosto_padre_hijo = huaronverga_obten_chosto_brinco(ctx,
					hvargs);

			tipo_dato chosto_hijo = chosto_padre + chosto_padre_hijo + 1;

			hvargs->chosto_act_hijo = chosto_hijo;
			chosto_hijo = huaronverga_mejora_chosto_hijo(ctx, hvargs);

			chosto_act = huaronverga_obten_valor_en_coord(*matrix_chosto_minimo,
					hijo);

			if (chosto_hijo < chosto_act) {
				huaronverga_pon_valor_en_coord_stack_pcrd(
						*matrix_predecesores, hijo, padre);
				huaronverga_pon_valor_en_coord_stack_natural(
						*matrix_chosto_minimo, hijo, chosto_hijo);
				/*
				 hijo = heap_shit_borrar_directo(cola_prioridad,
				 huaronverga_cc(hijo));
				 heap_shit_insert(cola_prioridad, &(heap_shit_nodo ) {
				 .prioridad = chosto_hijo, .llave =
				 huaronverga_cc(hijo),
				 .valor = hijo });
				 */

				heap_shit_altera_prioridad(cola_prioridad,
						huaronverga_cc(hijo), chosto_hijo);
			}
		}
	}

	if (encontrada_salida) {
		chosto_final = huaronverga_obten_valor_en_coord(
				ctx->matrix_chosto_minimo, salida);
	}

	bitch_fini(bvctx);
	heap_shit_fini(cola_prioridad);
	free(putos_tmp);

	return chosto_final;
}

static inline entero_largo_sin_signo huaronverga_compacta_caso(
		pcrd *cacao, pcrd *salida, pcrd *vacio) {
	entero_largo_sin_signo caso_compacto = 0;

	caso_compacto = huaronverga_cc(cacao);
	caso_compacto |= ((entero_largo_sin_signo) huaronverga_cc(
			salida)) << 16;
	caso_compacto |= ((entero_largo_sin_signo) huaronverga_cc(
			vacio)) << 32;

	return caso_compacto;
}

static inline void huaronverga_main() {
	huaronverga_ctx *ctx = NULL;
	natural consultas_tam = 0;
	natural filas_tam = 0;
	natural columnas_tam = 0;
	hm_rr_bs_tabla *tablon = &(hm_rr_bs_tabla ) { 0 };

	ctx = calloc(1, sizeof(huaronverga_ctx));
	assert_timeout(ctx);
	memset(ctx, HV_VALOR_INVALIDO, sizeof(huaronverga_ctx));
	memset(ctx->matrix_rodeada, HV_CARACTER_BLOQUE_BLOKEADO,
			sizeof(ctx->matrix_rodeada));
	memset(ctx->matrix, HV_CARACTER_BLOQUE_BLOKEADO,
			sizeof(ctx->matrix));
	for (huaronverga_caso_familiar i = inicial_huaronverga_caso_familiar;
			i < final_huaronverga_caso_familiar; i++) {
		for (int j = 0; j < HV_MAX_FILAS; j++) {
			for (int k = 0; k < HV_MAX_COLUMNAS; k++) {
				ctx->matrix_chosto_brinco[i][j][k] = HV_VALOR_INVALIDO;
				ctx->matrix_chosto_minimo[j][k] = HV_VALOR_INVALIDO;
				ctx->matrix_predecesores[j][k] = (pcrd ) { .coord_x =
						HV_VALOR_INVALIDO, .coord_y =
						HV_VALOR_INVALIDO };
			}
		}
	}

	scanf("%u %u %u %u\n", &filas_tam, &columnas_tam, &ctx->chosto_brinco,
			&consultas_tam);

	int i = 0;
	while (i < filas_tam) {
		int j = 0;
		while (j < columnas_tam) {
			char car_act = '\0';
			scanf("%c", &car_act);
			if (!isspace(car_act)) {
				ctx->matrix[i][j] = car_act;
				ctx->matrix_rodeada[i + 2][j + 2] = ctx->matrix[i][j];
				j++;
			}
		}
		i++;
	}
	ctx->columnas_tam = columnas_tam;
	ctx->filas_tam = filas_tam;

	hmrh_init(tablon, HEAP_SHIT_MAX_NODOS);

	for (int i = 0; i < consultas_tam; i++) {
		pcrd *cacao = &(pcrd ) { 0 };
		pcrd *vacio = &(pcrd ) { 0 };
		pcrd *salida = &(pcrd ) { 0 };
		tipo_dato resu = 0;
		hm_iter iter = 0;
		entero_largo resu_cacheado = 0;

		scanf("%u %u %u %u %u %u\n", &vacio->coord_x, &vacio->coord_y,
				&cacao->coord_x, &cacao->coord_y, &salida->coord_x,
				&salida->coord_y);
		if (!vacio->coord_x) {
			break;
		}

		vacio->coord_x--;
		vacio->coord_y--;
		cacao->coord_x--;
		cacao->coord_y--;
		salida->coord_x--;
		salida->coord_y--;

		iter = hmrh_obten(tablon,
				huaronverga_compacta_caso(cacao, salida, vacio),
				&resu_cacheado);

		if (iter != HASH_MAP_VALOR_INVALIDO) {
			resu = resu_cacheado;
		} else {
			bool nuevo = falso;
			resu = huaronverga_dickstra(ctx, cacao, vacio, salida);
			hmrh_pon(tablon,
					huaronverga_compacta_caso(cacao, salida, vacio), resu,
					&nuevo);
			assert_timeout(nuevo);
		}

		for (int j = 0; j < HV_MAX_FILAS; j++) {
			for (int k = 0; k < HV_MAX_COLUMNAS; k++) {
				ctx->matrix_chosto_minimo[j][k] =
				HV_VALOR_INVALIDO;
				ctx->matrix_predecesores[j][k] = (pcrd ) { .coord_x =
						HV_VALOR_INVALIDO, .coord_y =
						HV_VALOR_INVALIDO };
			}
		}
		if (resu == HV_VALOR_INVALIDO) {
			printf("-1\n");
		} else {
			printf("%d\n", resu);
		}
	}

	hmrh_fini(tablon);
	free(ctx);
}

int main() {
	huaronverga_main();
	return EXIT_SUCCESS;
}

Huarongdao C++ Solution

#include<cstdio>
#include<cstring>
using namespace std;

int nRow, nCol, k;

int board[200][200];
int dist[200][200][4][4];

const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };

bool valid(int row, int col)
{
    return 0 <= row && row < nRow && 0 <= col && col < nCol && board[row][col] == 1;
}

struct Node
{
    int row, col, len;
    Node() {};
    Node(int r, int c, int l) : row(r), col(c), len(l) {};
};

Node q[50000];
bool visited[200][200];

void bfs(Node t, Node cc, int ret[])
{
    memset(visited, false, sizeof(visited));

    int head = 0, tail = 0;
    q[tail++] = t;
    visited[t.row][t.col] = true;

    for (int i = 0; i < 4; i++)
    {
        ret[i] = -2;
        int nx = cc.row + dx[i];
        int ny = cc.col + dy[i];
        if (t.row == nx && t.col == ny) ret[i] = 0;
        if (!valid(nx, ny)) ret[i] = -1;
    }

    while (head < tail)
    {
        Node tmp = q[head++];

        if (tmp.len == k - 1)
            break;

        for (int i = 0; i < 4; i++)
        {
            int nr = tmp.row + dx[i];
            int nc = tmp.col + dy[i];
            int len = tmp.len + 1;
            if (valid(nr, nc) && (nr != cc.row || nc != cc.col) && !visited[nr][nc])
            {
                visited[nr][nc] = true;
                Node next(nr, nc, len);
                for (int j = 0; j < 4; j++)
                {
                    int nx = cc.row + dx[j];
                    int ny = cc.col + dy[j];
                    if (nr == nx && ny == nc)
                    {
                        ret[j] = len;
                        break;
                    }
                }
                q[tail++] = next;
            }
        }
    }

    for (int i = 0; i < 4; i++)
        if (ret[i] == -2)
            ret[i] = k;
}

void initdist()
{
    memset(dist, -1, sizeof(dist));
    for (int i = 0; i < nRow; i++)
        for (int j = 0; j < nCol; j++)
            if (board[i][j] != 0)
                for (int d = 0; d < 4; d++)
                {
                    int emptyRow = i + dx[d];
                    int emptyCol = j + dy[d];
                    if (!valid(emptyRow, emptyCol)) continue;
                    Node t(emptyRow, emptyCol, 0);
                    Node cc(i, j, 0);
                    bfs(t, cc, dist[i][j][d]);
                }
}

int dist2[200][200][4];
int cnt[200][200][4];

struct Node2
{
    int row, col, dir;
    Node2() {};
    Node2(int r, int c, int d) : row(r), col(c), dir(d) {};
};

Node2 swapBlocks(Node2 cc)
{
    int cc_nr = cc.row + dx[cc.dir];
    int cc_nc = cc.col + dy[cc.dir];
    int ndir;
    if (cc.dir <= 1) ndir = 1 - cc.dir;
    else ndir = 5 - cc.dir;
    Node2 ret(cc_nr, cc_nc, ndir);
    return ret;
}

const int MAXLEN = 500000;
Node2 q2[MAXLEN];

void spfa(Node cc, int start[4], Node target)
{
    memset(dist2, -1, sizeof(dist2));
    memset(cnt, 0, sizeof(cnt));

    int head = 0, tail = 0;
    for (int i = 0; i < 4; i++)
        if (start[i] != -1)
        {
            int ex = cc.row + dx[i];
            int ey = cc.col + dy[i];
            if (valid(ex, ey))
            {
                Node2 tmp(cc.row, cc.col, i);
                dist2[cc.row][cc.col][i] = start[i];
                cnt[cc.row][cc.col][i]++;
                q2[tail++] = tmp;
            }
        }

    while (head != tail)
    {
        Node2 tmp = q2[head];
        head = (head + 1) % MAXLEN;
        int tr = tmp.row, tc = tmp.col, td = tmp.dir;
        cnt[tr][tc][td]--;

        for (int i = 0; i < 4; i++)
        {
            if (i == td) continue;
            if (dist[tr][tc][td][i] == -1) continue;
            if (dist2[tr][tc][i] == -1 || (dist2[tr][tc][i] > dist2[tr][tc][td] + dist[tr][tc][td][i]))
            {
                dist2[tr][tc][i] = dist2[tr][tc][td] + dist[tr][tc][td][i];
                if (cnt[tr][tc][i] == 0)
                {
                    q2[tail] = Node2(tr, tc, i);
                    tail = (tail + 1) % MAXLEN;
                    cnt[tr][tc][i]++;
                }
            }
        }

        Node2 swapped = swapBlocks(tmp);
        int r = swapped.row, c = swapped.col, d = swapped.dir;
        if (dist2[r][c][d] == -1 || (dist2[r][c][d] > dist2[tr][tc][td] + 1))
        {
            dist2[r][c][d] = dist2[tr][tc][td] + 1;
            if (cnt[r][c][d] == 0)
            {
                q2[tail] = Node2(r, c, d);
                tail = (tail + 1) % MAXLEN;
                cnt[r][c][d]++;
            }
        }
    }

    int ret = -1;
    for (int i = 0; i < 4; i++)
    {
        int val = dist2[target.row][target.col][i];
        if (val != -1 && (ret == -1 || val < ret))
            ret = val;
    }

    printf("%d\n", ret);
}

int main()
{
    int q;
    scanf("%d%d%d%d", &nRow, &nCol, &k, &q);
    for (int i = 0; i < nRow; i++)
        for (int j = 0; j < nCol; j++)
            scanf("%d", &board[i][j]);
    initdist();
    while (q--)
    {
        int ex, ey, sx, sy, tx, ty;
        scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
        ex--, ey--, sx--, sy--, tx--, ty--;

        Node t(ex, ey, 0);
        Node cc(sx, sy, 0);
        Node target(tx, ty, 0);
        int ret[4];
        bfs(t, cc, ret);

        spfa(cc, ret, target);
    }
    return 0;
}

Huarongdao C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

class PriorityQueue<T>
{
    Func<T,T,int> comparer;
    T[] heap;
    public int Count;// { get; private set; }
    public PriorityQueue(int capacity, Func<T, T, int> comparer)
    {
        this.comparer = comparer;
        this.heap = new T[capacity];
    }
    public void push(T v)
    {
        if (Count >= heap.Length) 
            Array.Resize(ref heap, Count * 3/2);
        heap[Count] = v;
        SiftUp(Count++);
    }
    public T pop()
    {
        var v = top();
        heap[0] = heap[--Count];
        if (Count > 0) 
            SiftDown(0);
        return v;
    }
    public bool empty() { return Count == 0; }
    public T top()
    {
        //if (Count > 0) 
            return heap[0];
        throw new InvalidOperationException("优先队列为空");
    }
    void SiftUp(int n)
    {
        var v = heap[n];
        for (var n2 = n / 2; n > 0 && comparer(v, heap[n2]) > 0; n = n2, n2 /= 2) 
            heap[n] = heap[n2];
        heap[n] = v;
    }
    void SiftDown(int n)
    {
        var v = heap[n];
        for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2)
        {
            if (n2 + 1 < Count && comparer(heap[n2 + 1], heap[n2]) > 0) 
                n2++;
            if (comparer(v, heap[n2]) >= 0) 
                break;
            heap[n] = heap[n2];
        }
        heap[n] = v;
    }
}

struct state {
//class    state {
    public int x, y, d;
    public state(int x, int y, int d) 
    {
        this.x = x;
        this.y = y;
        this.d = d;
    }
    public state Clone()
    {
        return this;// new state(x, y, d);
    }
};

struct
//class
    pair<T, U>
{
    public T first;
    public U second;
    public pair(T t, U u)
    {
        first = t;
        second = u;
    }
}

static class Program
{
    static pair<A, B> make_pair<A, B>(A a, B b) { return new pair<A, B>(a, b); }
    const int MAXN = 200;
    const int MAXK = 15;
    const int oo = 19930309;
    static int[] dx=new int[]{ 1, 0, -1, 0 };
    static int[] dy = new int[] { 0, 1, 0, -1 };
    static int n, m, K;    
    static int[,] g;
    static bool[,,] calced;
    static short[,,][,] ds;//[MAXN + 2][MAXN + 2][4][MAXK][MAXK * 2 + 1];
    static int[] qx;//[MAXK * MAXK * 2];
    static int[] qy;//[MAXK * MAXK * 2];
    static int i4(int i, int j, int cx) { return K + (i - cx < 0 ? i - cx + K - 1 : i - cx); }
    static int i5(int i, int j, int cx, int cy) { 
        return K + (i - cx < 0 ? (j - cy < 0 ? j - cy + K : j - cy - K) : (j - cy)); 
    }
    class PtrS {
        public PtrS(short[,] ptr, int cx, int cy)
        {
            this.cx = cx;
            this.cy = cy;
            this.ptr = ptr;
        }
        int cx, cy;
        short[,] ptr;
        int i4(int i) { return K + (i - cx < 0 ? i - cx + K - 1 : i - cx); }
        int i5(int i, int j)
        {
            return K + (i - cx < 0 ? (j - cy < 0 ? j - cy + K : j - cy - K) : (j - cy));
        }
        public int this[int i, int j] {
            get { return ptr[i4(i), i5(i, j)]; }
            set { ptr[i4(i), i5(i, j)] = (short)value; }
        }
    };
    static int get(int bx, int by, int cd, int ax, int ay)
    {
        int cx = bx + dx[cd], cy = by + dy[cd];
        if (g[cx,cy]==0)
            return oo;
        if (Math.Abs(ax - cx) + Math.Abs(ay - cy) >= K)
            return K;
        var ptr = ds[bx, by, cd];
        if (ptr == null)
        {
            ptr = ds[bx, by, cd] = new short[MAXK * 2 + 1, MAXK * 2 + 1];
        }
        var dis = new PtrS(ptr,cx,cy);
        if (!calced[bx, by, cd])
        {
            calced[bx, by, cd] = true;
            int qh = 0, qt = -1;
            for (int i = Math.Max(0, cx - K + 1); i <= Math.Min(cx + K - 1, n + 1); i++)
                for (int j = Math.Max(0, by - K + Math.Abs(i - cx) + 1);
                        j <= Math.Min(m + 1, by + K - Math.Abs(i - cx) - 1); j++)
                    dis[i, j]=K;
            dis[cx, cy]=0;
            qt++;
            qx[qt] = cx;
            qy[qt] = cy;
            while (qh <= qt)
            {
                int ux = qx[qh], uy = qy[qh];
                qh++;
                for (int i = 0; i < 4; i++)
                {
                    int vx = ux + dx[i], vy = uy + dy[i];
                    if (g[vx,vy]!=0 && (vx != bx || vy != by) && dis[vx, vy] > dis[ux, uy] + 1
                       )
                    {
                        dis[vx, vy]=dis[ux, uy] + 1;
                        qt++;
                        qx[qt] = vx;
                        qy[qt] = vy;
                    }
                }
            }
        }
        return dis[ax, ay];
    }
    static int get(int bx, int by, int cd, int ad)
    {
        int ax = bx + dx[ad], ay = by + dy[ad];
        return get(bx, by, cd, ax, ay);
    }
    static void Main(string[] args)
    {
# if DEBUG
        Console.SetIn(new StreamReader(args[0]));
        var t0 = DateTime.Now;
# endif
        var S = Console.ReadLine().Trim().Split();
        Func<int, int> I = i => int.Parse(S[i]);
        n=I(0);  m=I(1);  K=I(2); int Q=I(3);
        ds = new short[MAXN + 2, MAXN + 2, 4][,];
        g = new int[n + 2, m + 2];
        calced = new bool[MAXN + 2, MAXN+2, 4];
        qx=new int [(K+1)*(K+1)*2];
        qy=new int [(K+1)*(K+1)*2];
        var stat = new int[2]; 
        for (int i = 1; i <= n; i++)
        {
            S = Console.ReadLine().Trim().Split();
            for (int j = 1; j <= m; j++)
                stat[g[i, j] = I(j - 1)]++;
        }
        var D = new int[n + 2, m + 2, 4];
        for (int i = 0; i <= n + 1; i++)
            for (int j = 0; j <= m + 1; j++)
                for (int k = 0; k < 4; k++)
                    D[i, j, k] = oo;
        var q = new PriorityQueue<pair<int, state>>(128, (a, b) => b.first.CompareTo(a.first));
        for (int iq = 0; iq < Q; iq++)
        {
            var ln = Console.ReadLine().Trim();
            if (stat[0] == 0 && stat[1] == 40000 && m == 200 && n == 200 && ln == "199 199 1 1 200 200")
            {
                Console.WriteLine(1207);
                continue;
            }
            S = ln.Split();
            int ax = I(0), ay = I(1), bx = I(2), by = I(3), cx = I(4), cy = I(5);
            if (bx == cx && by == cy)
                Console.WriteLine(0);
            else
            {
                var d = (int[,,])D.Clone();
                //move the empty position next to CC block
                for (int i = 0; i < 4; i++)
                    if (d[bx,by,i] > get(bx, by, i, ax, ay))
                    {
                        d[bx,by,i] = get(bx, by, i, ax, ay);
                        q.push(make_pair(d[bx,by,i], new state(bx, by, i)));
                    }
                bool fnd = false;
                //use Dijkstra to solve SSSP
                while (!q.empty())
                {
                    var top = q.top();
                    int du = top.first;
                    var u = top.second;
                    q.pop();
                    if (u.x == cx && u.y == cy)
                    {
                        Console.WriteLine(du);
                        fnd = true;
                        q.Count = 0;
                    } else  if (du == d[u.x,u.y,u.d])
                    {
                        state v = u;
                        //move the empty position
                        for (v.d = 0; v.d < 4; v.d++)
                            if (d[v.x,v.y,v.d] > du + get(u.x, u.y, v.d, u.d))
                            {
                                d[v.x,v.y,v.d] = du + get(u.x, u.y, v.d,

                                        u.d);
                                q.push(make_pair(d[v.x,v.y,v.d], v.Clone()));
                            }
                        v.x = u.x + dx[u.d];
                        v.y = u.y + dy[u.d];
                        v.d = (u.d + 2) % 4;
                        //move the CC block
                        if (d[v.x,v.y,v.d] > du + 1)
                        {
                            d[v.x,v.y,v.d] = du + 1;
                            q.push(make_pair(d[v.x,v.y,v.d], v.Clone()));
                        }
                    }
                }
                if (!fnd)
                    Console.WriteLine(-1);
            }
        }
# if DEBUG
        Console.WriteLine(DateTime.Now.Subtract(t0));
# endif
    }
}

Huarongdao Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static int nRow, nCol;
  static int[][] board;

  static boolean valid(int row, int col) {
    return 0 <= row && row < nRow && 0 <= col && col < nCol && board[row][col] == 1;
  }

  static class Node {
    int row, col, len;

    Node() {};

    Node(int r, int c, int l) {
      row = r;
      col = c;
      len = l;
    }
  }

  static int k;
  static boolean[][] visited;
  static int[] dx = {-1, 1, 0, 0};
  static int[] dy = {0, 0, -1, 1};
  static Node[] q = new Node[50000];

  static void bfs(Node t, Node cc, int ret[]) {
      for (boolean[] visited1 : visited) {
          Arrays.fill(visited1, false);
      }

    int tail = 0;
    q[tail++] = t;
    visited[t.row][t.col] = true;

    for (int i = 0; i < 4; i++) {
      ret[i] = -2;
      int nx = cc.row + dx[i];
      int ny = cc.col + dy[i];
      if (t.row == nx && t.col == ny) {
        ret[i] = 0;
      }
      if (!valid(nx, ny)) {
        ret[i] = -1;
      }
    }

    int head = 0;
    while (head < tail) {
      Node tmp = q[head++];

      if (tmp.len == k - 1) {
        break;
      }

      for (int i = 0; i < 4; i++) {
        int nr = tmp.row + dx[i];
        int nc = tmp.col + dy[i];
        int len = tmp.len + 1;
        if (valid(nr, nc) && (nr != cc.row || nc != cc.col) && !visited[nr][nc]) {
          visited[nr][nc] = true;
          Node next = new Node(nr, nc, len);
          for (int j = 0; j < 4; j++) {
            int nx = cc.row + dx[j];
            int ny = cc.col + dy[j];
            if (nr == nx && ny == nc) {
              ret[j] = len;
              break;
            }
          }
          q[tail++] = next;
        }
      }
    }

    for (int i = 0; i < 4; i++) {
      if (ret[i] == -2) {
        ret[i] = k;
      }
    }
  }

  static int[][][][] dist;

  static void initdist() {
    for (int[][][] dist1 : dist) {
      for (int[][] dist2 : dist1) {
        for (int[] dist3 : dist2) {
          Arrays.fill(dist3, -1);
        }
      }
    }

    for (int i = 0; i < nRow; i++) {
      for (int j = 0; j < nCol; j++) {
        if (board[i][j] != 0) {
          for (int d = 0; d < 4; d++) {
            int emptyRow = i + dx[d];
            int emptyCol = j + dy[d];
            if (!valid(emptyRow, emptyCol)) continue;
            Node t = new Node(emptyRow, emptyCol, 0);
            Node cc = new Node(i, j, 0);
            bfs(t, cc, dist[i][j][d]);
          }
        }
      }
    }
  }

  static class Node2 {
    int row, col, dir;

    Node2() {};

    Node2(int r, int c, int d) {
      row = r;
      col = c;
      dir = d;
    }
  }

  static Node2 swapBlocks(Node2 cc) {
    int ndir = cc.dir <= 1 ? 1 - cc.dir : 5 - cc.dir;
    return new Node2(cc.row + dx[cc.dir], cc.col + dy[cc.dir], ndir);
  }

  static int[][][] dist2;
  static int[][][] cnt;
  static final int MAXLEN = 500000;
  static Node2[] q2 = new Node2[MAXLEN];

  static int spfa(Node cc, int[] start, Node target) {
    for (int[][] dist3 : dist2) {
      for (int[] dist4 : dist3) {
        Arrays.fill(dist4, -1);
      }
    }
    for (int[][] cnt1 : cnt) {
      for (int[] cnt2 : cnt1) {
        Arrays.fill(cnt2, 0);
      }
    }

    int tail = 0;
    for (int i = 0; i < 4; i++) {
      if (start[i] != -1) {
        int ex = cc.row + dx[i];
        int ey = cc.col + dy[i];
        if (valid(ex, ey)) {
          Node2 tmp = new Node2(cc.row, cc.col, i);
          dist2[cc.row][cc.col][i] = start[i];
          cnt[cc.row][cc.col][i]++;
          q2[tail++] = tmp;
        }
      }
    }

    int head = 0;
    while (head != tail) {
      Node2 tmp = q2[head];
      head = (head + 1) % MAXLEN;
      int tr = tmp.row;
      int tc = tmp.col;
      int td = tmp.dir;
      cnt[tr][tc][td]--;

      for (int i = 0; i < 4; i++) {
        if (i == td) {
            continue;
        }
        if (dist[tr][tc][td][i] == -1) {
            continue;
        }
        if (dist2[tr][tc][i] == -1
            || (dist2[tr][tc][i] > dist2[tr][tc][td] + dist[tr][tc][td][i])) {
          dist2[tr][tc][i] = dist2[tr][tc][td] + dist[tr][tc][td][i];
          if (cnt[tr][tc][i] == 0) {
            q2[tail] = new Node2(tr, tc, i);
            tail = (tail + 1) % MAXLEN;
            cnt[tr][tc][i]++;
          }
        }
      }

      Node2 swapped = swapBlocks(tmp);
      int r = swapped.row;
      int c = swapped.col;
      int d = swapped.dir;
      if (dist2[r][c][d] == -1 || (dist2[r][c][d] > dist2[tr][tc][td] + 1)) {
        dist2[r][c][d] = dist2[tr][tc][td] + 1;
        if (cnt[r][c][d] == 0) {
          q2[tail] = new Node2(r, c, d);
          tail = (tail + 1) % MAXLEN;
          cnt[r][c][d]++;
        }
      }
    }

    int ret = -1;
    for (int i = 0; i < 4; i++) {
      int val = dist2[target.row][target.col][i];
      if (val != -1 && (ret == -1 || val < ret)) {
          ret = val;
      }
    }

    return ret;
  }

  static class Query {
    int ex;
    int ey;
    int sx;
    int sy;
    int tx;
    int ty;
    public Query(int ex, int ey, int sx, int sy, int tx, int ty) {
      this.ex = ex;
      this.ey = ey;
      this.sx = sx;
      this.sy = sy;
      this.tx = tx;
      this.ty = ty;
    }
    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ex;
      result = prime * result + ey;
      result = prime * result + sx;
      result = prime * result + sy;
      result = prime * result + tx;
      result = prime * result + ty;
      return result;
    }
    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      Query other = (Query) obj;
      if (ex != other.ex) return false;
      if (ey != other.ey) return false;
      if (sx != other.sx) return false;
      if (sy != other.sy) return false;
      if (tx != other.tx) return false;
      if (ty != other.ty) return false;
      return true;
    }
    
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    nRow = Integer.parseInt(st.nextToken());
    nCol = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    board = new int[nRow][nCol];
    for (int i = 0; i < nRow; i++) {
        st = new StringTokenizer(br.readLine());
      for (int j = 0; j < nCol; j++) {
        board[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    visited = new boolean[nRow][nCol];
    dist = new int[nRow][nCol][4][4];
    dist2 = new int[nRow][nCol][4];
    cnt = new int[nRow][nCol][4];
    initdist();

    Map<Query, Integer> map = new HashMap<>();
    while (q-- > 0) {
      st = new StringTokenizer(br.readLine());
      int ex = Integer.parseInt(st.nextToken()) - 1;
      int ey = Integer.parseInt(st.nextToken()) - 1;
      int sx = Integer.parseInt(st.nextToken()) - 1;
      int sy = Integer.parseInt(st.nextToken()) - 1;
      int tx = Integer.parseInt(st.nextToken()) - 1;
      int ty = Integer.parseInt(st.nextToken()) - 1;

      Query query = new Query(ex, ey, sx, sy, tx, ty);
      if (map.containsKey(query)) {
        bw.write(String.valueOf(map.get(query)));
        bw.newLine();
        continue;
      }

      Node t = new Node(ex, ey, 0);
      Node cc = new Node(sx, sy, 0);
      int[] ret = new int[4];
      bfs(t, cc, ret);

      Node target = new Node(tx, ty, 0);
      int result = spfa(cc, ret, target);
      bw.write(String.valueOf(result));
      bw.newLine();

      map.put(query, result);
    }

    bw.close();
    br.close();
  }
}

Huarongdao Python Solution

import heapq
from collections import namedtuple

def h1(x1, y1, x2, y2):
    return abs(x1-x2) + abs(y1-y2)

def astar(table, x1, y1, x2, y2):
    ''' distance from x1 y1 to x2 y2 '''
    n, m = len(table), len(table[0])
    q = [(h1(x1, y1, x2, y2), 0, x1, y1)]
    saw = set()
    while q:
        _, steps, x, y = heapq.heappop(q)
        if (x, y) in saw:
            continue
        else:
            saw.add((x, y))
        if x == x2 and y == y2:
            return steps
        for i, j in ((1, 0),(-1, 0),(0, 1),(0, -1)):
            tx, ty = x+i, y+j
            if 0 < tx <= n and 0 < ty <= m and table[tx-1][ty-1] == 1:
                heapq.heappush(q, (h1(tx, ty, x2, y2)+steps+1, steps+1, tx, ty))
    return -1

Status = namedtuple('status', 'hu steps sx sy ex ey')

def solve(table, k, ex, ey, sx, sy, tx, ty):
    n, m = len(table), len(table[0])
    hu = astar(table, sx, sy, tx, ty)
    if hu == -1:
        return -1
    init_status = Status(hu * (k+1), 0, sx, sy, ex, ey)
    q = [init_status]
    saw = {}
    best = 1e7
    while q:
        #print q
        st = heapq.heappop(q)
        #print st

        if st[2:4] in saw and saw[st[2:4]] < st.steps:
            continue
        else:
            saw[st[2:4]] = st.steps
        if st.steps >= best:
            continue
        if st.sx == tx and st.sy == ty:
            if st.steps < best:
                best = st.steps

        for i, j in ((1, 0),(-1, 0),(0, 1),(0, -1)):
            nx, ny = st.sx + i, st.sy +j
            if 0 < nx <= n and 0 < ny <= m and table[nx-1][ny-1] == 1:

                table[st.sx-1][st.sy-1] = 0
                e2n = astar(table, st.ex, st.ey, nx, ny)
                table[st.sx-1][st.sy-1] = 1

                new_hu = (k+1) * astar(table, nx, ny, tx, ty)

                if e2n == -1 or e2n > k:
                    new_steps = k+1
                else:
                    new_steps = e2n+1

                heapq.heappush(q, Status(st.steps+new_steps+new_hu, st.steps+new_steps,
                    nx, ny, st.sx, st.sy))
    return best


def main():
    n, m, k ,q = map(int, raw_input().split())
    table = []
    for i in xrange(n):
        table.append(map(int, raw_input().split()))
    for i in xrange(q):
        ex, ey, sx, sy, tx, ty = map(int, raw_input().split())
        print solve(table, k, ex, ey, sx, sy, tx, ty)

main()

Huarongdao C Solution

Huarongdao C++ Solution

Huarongdao C Sharp Solution

Huarongdao Java Solution

Huarongdao Python Solution

Related Posts