#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BIGNMB 300000

int drak_pos = 0;
int drak_z = 0;
int princess_count = 0;
int princess_pos[5] = {-1, -1, -1, -1, -1};
int generator = 0;
int generator_pos = 0;
int teleport_pos[3] = {-1,-1,-1};
int teleport_count = 0;
int teleport = 0;

struct listNode
{
	int dest;
	int weight;
	int pos;
	struct listNode *next;
};

struct list
{
	struct listNode *head;
};

struct Graph
{
	int V;
	struct list *array;
};

int getWeight(char letter)
{
	switch(letter)
	{
	case 'C':
		return 1;
	case 'H':
		return 2;
	case 'P':
		return 1;
	case 'N':
		return -1;
	case 'D':
		return 1;
	case 'G':
		return 1;
	}

	if(letter >= '0' && letter <= '9')
		return 1;

	return 0;
}

struct Graph *createGraph(int n, int m)
{
	int i;
	struct Graph *graph = (struct Graph*)malloc(sizeof(struct Graph));
	graph->V = n*m;

	graph->array = (struct list*)malloc(sizeof(struct list) * n * m);

	for(i=0;i<n*m;i++)
		graph->array[i].head = NULL;

	return graph;
}

struct listNode *newList(int dst, int weight, int pos)
{
	struct listNode* newNode = (struct listNode*)malloc(sizeof(struct listNode));
	newNode->dest = dst;
	newNode->weight = weight;
	newNode->pos = pos;
	newNode->next = NULL;

	return newNode;
}

void addEdge(struct Graph *graph, int src, int dst, int weight)
{
	struct listNode *newNode = newList(dst, weight, src);
	newNode->next = graph->array[src].head;
	graph->array[src].head = newNode;
}

struct minHeapNode
{
	int v;
	int dist;
};

struct minHeap
{
	int size;
	int capacity;
	int *pos;
	struct minHeapNode **array;
};

struct minHeapNode *newMinHeapNode(int v, int dist)
{
	struct minHeapNode *min_heap_node = (struct minHeapNode*)malloc(sizeof(struct minHeapNode));
	min_heap_node->v = v;
	min_heap_node->dist = dist;
	return min_heap_node;
}

struct minHeap *createMinHeap(int capacity)
{
	struct minHeap *min_heap = NULL;
	min_heap = (struct minHeap*)malloc(sizeof(struct minHeap));
	min_heap->pos = (int*)malloc(capacity*sizeof(int));
	min_heap->size = 0;
	min_heap->capacity = capacity;
	min_heap->array = (struct minHeapNode**)malloc(sizeof(struct minHeapNode*) * capacity);
	return min_heap;
}

void minHeapify(struct minHeap *min_heap, int id)
{
	int smallest, left, right;
	struct minHeapNode *smallestNode, *idNode, *tmp;
	smallest = id;
	left = 2 * id + 1;
	right = 2 * id + 2;

	if(left < min_heap->size && min_heap->array[left]->dist < min_heap->array[smallest]->dist)
		smallest = left;

	if(right < min_heap->size && min_heap->array[right]->dist < min_heap->array[smallest]->dist)
		smallest = right;

	if(smallest != id)
	{
		smallestNode = min_heap->array[smallest];
		idNode = min_heap->array[id];

		min_heap->pos[smallestNode->v] = id;
		min_heap->pos[idNode->v] = smallest;

		tmp = min_heap->array[smallest];
		min_heap->array[smallest] = min_heap->array[id];
		min_heap->array[id] = tmp;
		minHeapify(min_heap, smallest);
	}
}

int isEmpty(struct minHeap *min_heap)
{
	return min_heap->size == 0;
}

struct minHeapNode *takeMin(struct minHeap *min_heap)
{
	struct minHeapNode *root, *lastNode;

	if (isEmpty(min_heap))
		return NULL;

	root = min_heap->array[0];
	lastNode = min_heap->array[min_heap->size - 1];
	min_heap->array[0] = lastNode;

	min_heap->pos[root->v] = min_heap->size-1;
	min_heap->pos[lastNode->v] = 0;

	--min_heap->size;
	minHeapify(min_heap, 0);

	return root;
}

void decrease(struct minHeap *min_heap, int v, int dist)
{
	struct minHeapNode *tmp;
	int i = min_heap->pos[v];
	min_heap->array[i]->dist = dist;

	while(i && min_heap->array[i]->dist < min_heap->array[(i-1)/2]->dist)
	{
		min_heap->pos[min_heap->array[i]->v] = (i-1)/2;
		min_heap->pos[min_heap->array[(i-1)/2]->v] = i;

		tmp = min_heap->array[i];
		min_heap->array[i] = min_heap->array[(i-1)/2];
		min_heap->array[(i-1)/2] = tmp;

		i = (i-1)/2;
	}
}

int isInMinHeap(struct minHeap *min_heap, int v)
{
	if(min_heap->pos[v] < min_heap->size)
		return 1;
	return 0;
}

int *dijkstra(struct Graph *graph, int src, int *cesta, int m)
{
	int V = graph->V, v, u, *parent;
	int *dist;
	struct minHeap *min_heap = createMinHeap(V);
	struct minHeapNode *min_heap_node;
	struct listNode *pNode;

	dist = (int*)malloc(sizeof(int)*V);
	parent = (int*)malloc(sizeof(int)*V);

	for(v = 0; v < V; ++v)
	{
		parent[0] = -1;
		dist[v] = BIGNMB;
		min_heap->array[v] = newMinHeapNode(v, dist[v]);
		min_heap->pos[v] = v;
	}

	min_heap->array[src] = newMinHeapNode(src, dist[src]);
	min_heap->pos[src] = src;
	dist[src] = 0;
	decrease(min_heap, src, dist[src]);

	min_heap->size = V;

	while(!isEmpty(min_heap))
	{
		min_heap_node = takeMin(min_heap);
		u = min_heap_node->v;

		pNode = graph->array[u].head;
		while(pNode != NULL)
		{
			v = pNode->dest;
			if(isInMinHeap(min_heap, v) && dist[u] != BIGNMB && pNode->weight + dist[u] < dist[v])
			{
				dist[v] = dist[u] + pNode->weight;
				parent[v] = u;
				decrease(min_heap, v, dist[v]);
			}
			if(pNode->pos == drak_pos && drak_z == 0) {
				drak_z = 1;
				return parent;
			}

			if(pNode->pos == generator_pos)
                generator = 1;

			if((pNode->pos == teleport_pos[0] || pNode->pos == teleport_pos[1] || pNode->pos == teleport_pos[2]) && drak_z == 1 && generator == 1 && teleport == 0)
			{
				teleport = 1;
				teleport_pos[0] = -1;
				*cesta = princess_pos[0];
				return parent;
			}

			if(pNode->pos == princess_pos[0] && drak_z == 1)
			{
				*cesta = princess_pos[0];
				princess_pos[0] = -1;
				return parent;
			}

			if(pNode->pos == princess_pos[1] && drak_z == 1)
			{
				*cesta = princess_pos[1];
				princess_pos[1] = -1;
				return parent;
			}

			if(pNode->pos == princess_pos[2] && drak_z == 1)
			{
				*cesta = princess_pos[2];
				princess_pos[2] = -1;
				return parent;
			}

			if(pNode->pos == princess_pos[3] && drak_z == 1)
			{
				*cesta = princess_pos[3];
				princess_pos[3] = -1;
				return parent;
			}

			if(pNode->pos == princess_pos[4] && drak_z == 1)
			{
				*cesta = princess_pos[4];
				princess_pos[4] = -1;
				return parent;
			}

			pNode = pNode->next;
		}
	}
	return 0;
}

int *zachran_princezne(char **mapa, int n, int m, int t, int *dlzka_cesty)
{
	int i, j, poc = 0, *dist, *path, cesta, l, k, *tmp, totalCount = 0, o, pred;
	struct Graph* graph = createGraph(n,m);

	path = (int*)malloc(sizeof(int)*n*m);
	tmp = (int*)malloc(sizeof(int)*n*m);

	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{

			if(mapa[i][j] == 'D')
				drak_pos = poc;

			if(mapa[i][j] == 'P')
			{
				princess_pos[princess_count] = poc;
				princess_count++;
			}

			if(mapa[i][j] == 'G')
				generator_pos = poc;

			if(mapa[i][j] == '0')
			{
				teleport_pos[teleport_count] = poc;
				teleport_count++;
			}

			if(j==0 && i==0)
			{
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j!=0 && i==0 && j != m-1)
			{
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j==m-1 && i==0)
			{
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j==0 && i==n-1)
			{
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j!=0 && i==n-1 && j!=m-1)
			{
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j==m-1 && i==n-1)
			{
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j==0 && i!=0 && i!=n-1)
			{
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j==m-1 && i!=0 && i!=n-1)
			{
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				poc++;
			}
			else if(j!=0 && i!=0 && i!=n-1 && j!= m-1)
			{
				addEdge(graph, poc, poc-m, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc-1, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+m, getWeight(mapa[i][j]));
				addEdge(graph, poc, poc+1, getWeight(mapa[i][j]));
				poc++;
			}
		}
	}

	dist = dijkstra(graph, 0, &cesta, m);
	path[0] = 0;
	path[1] = 0;
	k = drak_pos;
	i=1;
	while(1)
	{
		tmp[i] = k;
		i++;
		k = dist[k];
		totalCount++;
		if(k==0)
			break;
	}

	 l = totalCount;
     for (i = 1; i <= totalCount; i++){
		path[i*2] = tmp[l] % m;
        path[i*2+1] = tmp[l] / m;
        l--;
     }

	for(j=0;j<princess_count;j++)
	{
			if(j==0)
			{
				dist = dijkstra(graph, drak_pos, &cesta, m);
				k = cesta;
				pred = drak_pos;
			}
			else
			{
				dist = dijkstra(graph, pred, &cesta, m);
				k = cesta;
			}
		if(cesta != -1) {
			i=0;
			while(1)
			{
				tmp[i] = k;
				i++;
				k = dist[k];
				totalCount++;
				if(j==0) {
					if(k==drak_pos)
						break;
				}
				else
				{
					if(k==pred)
						break;
				}
			}

			 l = i-1;
			 for (o = totalCount-i+1; o <= totalCount; o++){
				path[o*2] = tmp[l] % m;
				path[o*2+1] = tmp[l] / m;
				l--;
			 }
			pred = cesta;
		}
		else
		{
			k = 8;
			i=0;
			while(1)
			{
				tmp[i] = k;
				i++;
				k = dist[k];
				totalCount++;
				if(j==0) {
					if(k==drak_pos)
						break;
				}
				else
				{
					if(k==pred)
						break;
				}
			}

			 l = i-1;
			 for (o = totalCount-i+1; o <= totalCount; o++){
				path[o*2] = tmp[l] % m;
				path[o*2+1] = tmp[l] / m;
				l--;
			 }
		}
	}

	if(teleport == 1) {
        dist = dijkstra(graph, 35, &cesta, m);
		k = cesta;
		i=0;
		while(1)
		{
			tmp[i] = k;
			i++;
			k = dist[k];
			totalCount++;
			if(k==35)
				break;
		}
		tmp[i] = 35;
		i++;
		totalCount++;
		l = i-1;
		for (i = totalCount-i+1; i <= totalCount; i++){
			path[i*2] = tmp[l] % m;
			path[i*2+1] = tmp[l] / m;
			l--;
		 }

    }
	*dlzka_cesty = totalCount+1;

	return path;
}


int main()
{
	int dlzka_cesty, i, *path;
	char **mapa;
	mapa = (char**)malloc(7*sizeof(char*));


	for(i=0;i<7;i++)
		mapa[i] = (char*)malloc(sizeof(char) * 7);

	mapa[0] = "HGHPCDC";
	mapa[1] = "C0CCHPP";
	mapa[2] = "HHHHHCH";
	mapa[3] = "HHHHHHC";
	mapa[4] = "0CCCHCH";
	mapa[5] = "0CHCH1C";
	mapa[6] = "CPCCCHH";


	path = zachran_princezne(mapa, 7, 7, 100, &dlzka_cesty);

	for (i=0;i<dlzka_cesty;++i)
		printf("%d %d\n", path[i*2], path[i*2+1]);

}