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


struct pos {
	int x;
	int y;
	struct pos * next;
};


struct pos *
pos_create(int x, int y, struct pos * next)
{
	struct pos * p = malloc(sizeof(struct pos));
	if (!p)
		return NULL;
	p->x = x;
	p->y = y;
	p->next = next;
	return p;
}


void
pos_free(struct pos * p)
{
	if (!p)
		return;
	pos_free(p->next);
	free(p);
}


int
visited(unsigned char c)
{
	return c & 0x80;
}


int
height(unsigned char c)
{
	c &= 0x7F;

	switch (c) {
	case 'S': return 'a';
	case 'E': return 'z';
	}
	return c;
}


int
tryvisit(unsigned char * range, int cols, int rows, struct pos const * from, int dx, int dy)
{
	int x, y;
	unsigned char src, dst;

	x = from->x + dx;
	y = from->y + dy;

	// Check bounds.
	if (x < 0 || x >= cols - 1
			|| y < 0 || y >= rows)
		return 0;

	// Check if already visited
	dst = range[x + y * cols];
	if (visited(dst))
		return 0;

	// Check height
	src = range[from->x + from->y * cols];
	if (height(dst) > height(src) + 1)
		return 0;

	// OK. We can visit, so mark the new position as visited.
	range[x + y * cols] |= 0x80;

	return 1;
}


int
main()
{
	unsigned char * range, * p;
	size_t rangesize, rangelen, bytes;
	int cols, rows;
	struct pos * front;
	int steps;

	// Read hill range
	rangesize = BUFSIZ;
	rangelen = 0;
	range = malloc(rangesize);
	while ((bytes = fread(range + rangelen, 1, rangesize - rangelen, stdin)) > 0) {
		rangelen += bytes;
		if (rangelen == rangesize) {
			rangesize += BUFSIZ;
			if ((p = realloc(range, rangesize)) == NULL) {
				fprintf(stderr, "realloc(%zu) failed\n", rangesize);
				free(range);
				return -1;
			}
			range = p;
		}
	}

	// Get cols/rows in hill range
	if ((p = memchr(range, '\n', rangelen)) == NULL) {
		fprintf(stderr, "No lines found in input!\n");
		free(range);
		return -1;
	}
	cols = p - range + 1;
	if (rangelen % cols != 0) {
		fprintf(stderr, "Input length %zu is not a multiple of line length %d\n",
				rangelen, cols);
		free(range);
		return -1;
	}
	rows = rangelen / cols;

	// Find start, and mark it as visited
	if ((p = memchr(range, 'S', rangelen)) == NULL) {
		fprintf(stderr, "No start position!\n");
		free(range);
		return -1;
	}
	front = pos_create((p - range) % cols, (p - range) / cols, NULL);
	range[front->x + front->y * cols] |= 0x80;

	// Take steps, widening the search front each iteration.
	for (steps = 0; front != NULL; ++steps) {
		struct pos * nextfront = NULL;
		struct pos * loc;

		for (loc = front; loc != NULL; loc = loc->next) {
			if ((range[loc->x + loc->y * cols] & 0x7F) == 'E')
				// We found the end point!
				break;

			if (tryvisit(range, cols, rows, loc, -1, 0))
				nextfront = pos_create(loc->x - 1, loc->y, nextfront);
			if (tryvisit(range, cols, rows, loc, +1, 0))
				nextfront = pos_create(loc->x + 1, loc->y, nextfront);
			if (tryvisit(range, cols, rows, loc, 0, -1))
				nextfront = pos_create(loc->x, loc->y - 1, nextfront);
			if (tryvisit(range, cols, rows, loc, 0, +1))
				nextfront = pos_create(loc->x, loc->y + 1, nextfront);
		}
		if (loc) {
			// Create a duplicate of the final location at the start
			// of the current search front
			front = pos_create(loc->x, loc->y, front);
			pos_free(nextfront);
			break;
		}

		pos_free(front);
		front = nextfront;
	}

	if (front)
		printf("Found end at %d,%d in %d steps\n", front->x, front->y, steps);
	else
		printf("No end found after %d steps\n", steps);

	pos_free(front);
	free(range);

	return 0;
}