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


#define C_EMPTY	0x00

#define C_BLZ_N	0x01
#define C_BLZ_E	0x02
#define C_BLZ_S 0x04
#define C_BLZ_W	0x08

#define C_BLZ	(C_BLZ_N | C_BLZ_E | C_BLZ_S | C_BLZ_W)

#define C_WALL  0x10
#define C_ELF	0x20


unsigned char *
pos(unsigned char * buf, int cols, int rows, int i, int j)
{
	i = ((i % cols) + cols) % cols;
	j = ((j % rows) + rows) % rows;

	return buf + i + j * cols;
}


int
main()
{
	unsigned char * buf = NULL, * next = NULL;
	int bufsiz = 0, buflen = 0;
	int cols = -1, rows = -1, exit_col = -1, exit_row = -1;
	int i, j, round;

	// Read input
	while (1) {
		if (bufsiz - buflen < BUFSIZ) {
			void * p;

			bufsiz += BUFSIZ;
			if ((p = realloc(buf, bufsiz)) == NULL) {
				fprintf(stderr, "Bad realloc(%d)\n", bufsiz);
				free(buf);
				return -1;
			}
			buf = p;
		}

		if ((i = fgetc(stdin)) == EOF)
			break;
		switch (i) {
		case '#':
			buf[buflen++] = C_WALL;
			break;

		case '.':
			if (cols == -1)
				buf[buflen++] = C_ELF;
			else
				buf[buflen++] = C_EMPTY;
			break;

		case '^':
			buf[buflen++] = C_BLZ_N;
			break;

		case '>':
			buf[buflen++] = C_BLZ_E;
			break;

		case 'v':
			buf[buflen++] = C_BLZ_S;
			break;

		case '<':
			buf[buflen++] = C_BLZ_W;
			break;

		case '\n':
			if (cols == -1)
				cols = buflen;
			break;

		default:
			fprintf(stderr, "Unexpected input char %c\n", i);
			return -1;
		}
	}
	if (cols == -1 || buflen % cols != 0) {
		fprintf(stderr, "Input size %d is not a multiple of row length %d\n",
				buflen, cols);
		free(buf);
		return -1;
	}
	rows = buflen / cols;

	// Find the exit position
	exit_row = rows - 1;
	for (i = 0; i < cols; ++i) {
		if (*pos(buf, cols, rows, i, exit_row) == C_EMPTY)
			exit_col = i;
	}
	if (exit_col == -1) {
		fprintf(stderr, "No exit position found!\n");
		free(buf);
		return -1;
	}

	// Create the "next" buffer, and place the walls in it.
	if ((next = calloc(buflen, 1)) == NULL) {
		fprintf(stderr, "Bad next alloc(%d)\n", buflen);
		free(buf);
		return -1;
	}
	for (i = 0; i < buflen; ++i) {
		if (buf[i] == C_WALL)
			next[i] = C_WALL;
	}

	for (round = 0; (*pos(buf, cols, rows, exit_col, exit_row) & C_ELF) == 0; ++round) {
		int elves = 0;
		unsigned char * psrc, * pdest, * tmp;

		// Work out the possible positions of elves and blizzards in `next`
		for (j = 0; j < rows; ++j) {
			for (i = 0; i < cols; ++i) {
				int o;

				psrc = pos(buf, cols, rows, i, j);

				if (*psrc & C_ELF) {
					*pos(next, cols, rows, i, j) |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i, j - 1)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i + 1, j)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i, j + 1)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i - 1, j)) & C_WALL) == 0)
						*pdest |= C_ELF;
					++elves;
				}
				if (*psrc & C_BLZ_N) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i, j - o)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_N;
				}
				if (*psrc & C_BLZ_E) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i + o, j)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_E;
				}
				if (*psrc & C_BLZ_S) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i, j + o)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_S;
				}
				if (*psrc & C_BLZ_W) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i - o, j)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_W;
				}
			}
		}
		if (elves == 0) {
			fprintf(stderr, "Warning, ran out of elves after %d rounds!\n", round);
			free(next);
			free(buf);
			return -1;
		}

		// Whereever there is a blizzard and and elf together, remove the elf
		for (j = 0; j < rows; ++j) {
			for (i = 0; i < cols; ++i) {
				if ((*(pdest = pos(next, cols, rows, i, j)) & C_ELF) != 0
						&& (*pdest & C_BLZ) != 0)
				{
					*pdest &= ~C_ELF;
				}
			}
		}

		// Swap next and buf, and clear `next` for next round
		tmp = buf;
		buf = next;
		next = tmp;
		for (j = 0; j < rows; ++j) {
			for (i = 0; i < cols; ++i) {
				if ((*(pdest = pos(next, cols, rows, i, j)) & C_WALL) == 0)
					*pdest = C_EMPTY;
			}
		}
	}

	printf("Found exit after %d rounds\n", round);

	// Tidy and exit
	free(next);
	free(buf);

	return 0;
}