• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

Huarongdao – HackerRank Solution

Huarongdao - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 27, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • Huarongdao – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
  • Solutions of Algorithms Data Structures Hard HackerRank:
    • Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
  • C++ Huarongdao HackerRank Solution
  • Java Huarongdao HackerRank Solution
  • Python 2 Huarongdao HackerRank Solution
  • C Huarongdao HackerRank Solution
    • Leave a comment below
      • Related posts:

Huarongdao – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Solutions of Algorithms Data Structures Hard HackerRank:

Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

C++ Huarongdao HackerRank Solution


Copy Code Copied Use a different Browser

#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <vector>

using namespace std;

#define output(x) cout << #x << ": " << (x) << endl;

typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<double> VD;
typedef vector<string> VS;

const int max_n = 200 + 10, max_m = max_n;
const int delta[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int n, m, cheat, q, cost[max_n][max_m][4][4], total[max_n][max_m][4];
char board[max_n][max_m];
map<pair<int, int>, int> cost_map;
bool in[max_n][max_m][4];

void bfs(int x0, int y0, int fx, int fy, int limit) {
    queue<pair<int, int> > q;
    cost_map.clear();
    q.push(make_pair(x0, y0));
    cost_map[q.front()] = 0;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second, c = cost_map[q.front()];
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + delta[i][0], ny = y + delta[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || board[nx][ny] == 0 || (nx == fx && ny == fy))
                continue;
            pair<int, int> k(nx, ny);
            if (cost_map.find(k) != cost_map.end())
                continue;
            if (c + 1 < limit)
                q.push(k);
            cost_map[k] = c + 1;
        }
    }
}

void pre_compute() {
    memset(cost, -1, sizeof(cost));
    for (int x0 = 0; x0 < n; ++x0) {
        for (int y0 = 0; y0 < m; ++y0) {
            if (board[x0][y0] == 0)
                continue;
            for (int k = 0; k < 4; ++k) {
                int x1 = x0 + delta[k][0], y1 = y0 + delta[k][1];
                if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m || board[x1][y1] == 0)
                    continue;
                bfs(x0, y0, x1, y1, cheat - 1);
                for (int step = 0; step < 4; ++step) {
                    int x2 = x1 + delta[step][0], y2 = y1 + delta[step][1];
                    if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || board[x2][y2] == 0 || (x2 == x0 && y2 == y0))
                        continue;
                    cost[x0][y0][k][step] = cheat + 1;
                    map<pair<int, int>, int>::iterator it = cost_map.find(make_pair(x2, y2));
                    if (it != cost_map.end())
                        cost[x0][y0][k][step] = it->second + 1;
                }
            }
        }
    }
}

int process() {
    int ex, ey, x0, y0, tx, ty;
    scanf("%d%d%d%d%d%d", &ex, &ey, &x0, &y0, &tx, &ty);
    --ex; --ey; --x0; --y0; --tx; --ty;
    if (x0 == tx && y0 == ty)
        return 0;
    if (ex == x0 && ey == y0)
        return -1;
    bfs(ex, ey, x0, y0, cheat - 1);
    queue<pair<pair<int, int>, int> > q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                in[i][j][k] = false;
                total[i][j][k] = INT_MAX;
            }
        }
    }
    for (int k = 0; k < 4; ++k) {
        int x1 = x0 + delta[k][0], y1 = y0 + delta[k][1];
        if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m || board[x1][y1] == 0)
            continue;
        q.push(make_pair(make_pair(x0, y0), k));
        in[x0][y0][k] = true;
        total[x0][y0][k] = cheat + 1;
        map<pair<int, int>, int>::iterator it = cost_map.find(make_pair(x1, y1));
        if (it != cost_map.end())
            total[x0][y0][k] = it->second + 1;
    }
    while (!q.empty()) {
        int x0 = q.front().first.first, y0 = q.front().first.second;
        int k = q.front().second, c = total[x0][y0][k];
        q.pop();
        int x1 = x0 + delta[k][0], y1 = y0 + delta[k][1];
        for (int step = 0; step < 4; ++step) {
            if (cost[x0][y0][k][step] == -1)
                continue;
            if (c + cost[x0][y0][k][step] < total[x1][y1][step]) {
                if (!in[x1][y1][step]) {
                    q.push(make_pair(make_pair(x1, y1), step));
                    in[x1][y1][step] = true;
                }
                total[x1][y1][step] = c + cost[x0][y0][k][step];
            }
        }
    }
    int res = INT_MAX;
    for (int x0 = 0; x0 < n; ++x0)
        for (int y0 = 0; y0 < m; ++y0)
            for (int k = 0; k < 4; ++k)
                if (x0 + delta[k][0] == tx && y0 + delta[k][1] == ty)
                    res = min(res, total[x0][y0][k]);
    return res == INT_MAX ? -1 : res;
}

void solve() {
    scanf("%d%d%d%d", &n, &m, &cheat, &q);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            scanf("%d", &board[i][j]);
    pre_compute();
    for (int i = 0; i < q; ++i)
        printf("%d\n", process());
}

int main() {
    solve();
    return 0;
}

Java Huarongdao HackerRank Solution


Copy Code Copied Use a different Browser

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;


public class Solution {
	static int a[][];
	static int n, m, cheat, q, ex, ey, sx, sy, tx, ty;
	static boolean visited[][];
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	
	static class CB {
		int x;
		int y;
		public CB(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override public int hashCode() {
			int res = 17;
			res = res * 31 + x;
			res = res * 31 + y;
			return res;
		}
		@Override public boolean equals(Object o) {
			if (!(o instanceof CB)) return false;
			CB cb = (CB)o;
			return x == cb.x && y == cb.y;
		}
		@Override public String toString() {
			return String.format("(%d, %d)", x, y);
		}
	}
	
	static boolean isok(int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 1;
	}
	
	static int bfs(CB start, CB end) {
		Map<CB, Integer> map = new HashMap<CB, Integer>();
		map.put(start, 0);
		Queue<CB> queue = new ArrayDeque<CB>();
		queue.add(start);
		
		while(!queue.isEmpty()) {
			CB head = queue.poll();
			int dist = map.get(head);
			if (dist >= cheat) return -1;
			if (head.equals(end)) return dist;
			
			for (int k=0; k<dx.length; k++) {
				int x = head.x + dx[k];
				int y = head.y + dy[k];
				
				CB nextStep = new CB(x, y);
				if (isok(x, y)  && !map.containsKey(nextStep)) {
					map.put(nextStep, dist + 1);
					queue.add(nextStep);
				}
			}
		}
		return -1;
	}
	
	static int queue[] = new int[222 * 222 * 20];
	
	static int doit(CB caocaoInit, CB exit, CB emptyInit) {
		if (caocaoInit.equals(exit)) return 0;
		
		int d[] = new int[vIndex];
		Arrays.fill(d, -1);
		
		boolean visited[] = new boolean[vIndex];
		int head = 0, tail = 0;
		
		
		// do not forget
		a[caocaoInit.x][caocaoInit.y] = 0; 
		for (int i=0; i<4; i++) {
			int x = caocaoInit.x + dx[i];
			int y = caocaoInit.y + dy[i];
			int time = -1;
			if (isok(x, y)) {
				time = bfs(emptyInit, new CB(x, y));
				if (time < 0 || time > cheat) time = cheat;
			
				if (new CB(x, y).equals(exit)) {
					a[caocaoInit.x][caocaoInit.y] = 0;
					return time + 1;
				}
			
				int u = stateIndex[caocaoInit.x][caocaoInit.y][i];
				d[u] = time;
				queue[tail++] = u;
				visited[u] = true;
			}
		}
		a[caocaoInit.x][caocaoInit.y] = 1;
		
		
		while(head != tail) {
			int u = queue[head++];
			if (head == queue.length) head = 0;
			visited[u] = false;
			
			for (Edge edge : e[u]) {
				int v = edge.v;
				int w = edge.w;
				if (d[v] == -1 || d[u] + w < d[v]) {
					d[v] = d[u] + w;
					if (!visited[v]) {
						visited[v] = true;
						queue[tail++] = v;
						if (tail == queue.length) tail = 0;
					}
				}
			}
		}
		
		
		int ans = Integer.MAX_VALUE;
		for (int i=0; i<vIndex; i++)
			if (vInverse[i].equals(exit) && d[i] > -1 && d[i] < ans) ans = d[i];
		
		
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}
	
	static class Edge {
		int v, w;
		public Edge(int v, int w) {
			this.v = v;
			this.w = w;
		}
		@Override public String toString() {
			return String.format("( v = %s, w = %d )", vInverse[v], w);
		}
	}
	
	@SuppressWarnings("unchecked")
	static ArrayList<Edge> e[] = new ArrayList[222 * 222 * 222];
	static int vIndex = 0;
	static CB vInverse[] = new CB[222 * 222 * 222]; 
	static int dirInverse[] = new int[222 * 222 * 222];
	static int stateIndex[][][];
	
	static int twin(int k) {
		if (k == 0) return 1;
		else if (k == 1) return 0;
		else if (k == 2) return 3;
		else return 2;
	}
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		n = cin.nextInt();
		m = cin.nextInt();
		cheat = cin.nextInt(); 
		q = cin.nextInt();
		a = new int[n][m];
		stateIndex = new int[n][m][4];
		for (int i=0; i<n; i++) 
			for (int j=0; j<m; j++)
				a[i][j] = cin.nextInt();

		for (int i=0; i<n; i++)
			for (int j=0; j<m; j++)
				for (int k=0; k<4; k++) {
					vInverse[vIndex] = new CB(i, j);
					dirInverse[vIndex] = k;
					stateIndex[i][j][k] = vIndex++;
				}
		
		for (int i=0; i<vIndex; i++)
			e[i] = new ArrayList<Edge>();
		
		for (int i=0; i<n; i++)
			for (int j=0; j<m; j++) {
				if (a[i][j] == 0) continue;
				
				a[i][j] = 0;
				
				for (int k=0; k<4; k++) {
					int u = stateIndex[i][j][k];
					
					int x = i + dx[k];
					int y = j + dy[k];
					if (!isok(x, y)) continue;
					
					for (int l=0; l<4; l++) {
						int xx = i + dx[l];
						int yy = j + dy[l];
						if (!isok(xx, yy)) continue;
						
						int v = stateIndex[xx][yy][twin(l)];
						int w = bfs(new CB(x, y), new CB(xx, yy));
						if (w < 0 || w > cheat) w = cheat;
						w++;
						e[u].add(new Edge(v, w));
					}	
				}
				a[i][j] = 1;
			}
		
		
		for (int T=0; T<q; T++) {
			ex = cin.nextInt() - 1;
			ey = cin.nextInt() - 1;
			sx = cin.nextInt() - 1;
			sy = cin.nextInt() - 1;
			tx = cin.nextInt() - 1;
			ty = cin.nextInt() - 1;
			
			System.out.println(doit(new CB(sx, sy), new CB(tx, ty), new CB(ex, ey)));
		}
		cin.close();
	}

}

 




Python 2 Huarongdao HackerRank Solution


Copy Code Copied Use a different Browser

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()



C Huarongdao HackerRank Solution


Copy Code Copied Use a different Browser

#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;
}

 

Leave a comment below

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Strings Game – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaximizing Mission Points – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionPlus Minus – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTree: Preorder Traversal – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFloyd : City of Blinding Lights – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHacker Country – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank SolutionHuarongdaojavajava 15java 7java 8java8javascriptpypy 3Python 2python 3
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
29

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

HackerX - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Jim and his LAN Party - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionTwo Strings Game – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaximizing Mission Points – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionPlus Minus – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTree: Preorder Traversal – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFloyd : City of Blinding Lights – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHacker Country – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions
Code Solutions

Maximal Rectangle – LeetCode Solution

September 3, 2022
72
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Dijkstra: Shortest Reach 2 – HackerRank Solution

May 26, 2022
276
Shark Tank
Business

Hidrent Net Worth 2022 – What Happened After Shark Tank? Everything You need to know.

September 4, 2022
0
Shark Tank
Business

What Happened To Five Minute Furniture After Shark Tank? Everything you need to know.

September 3, 2022
2

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?