cycle.c

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

typedef struct Node Node;
struct Node {
    Node *next;  /* next Node in the chain       */
    Node *first; /* Node we started the chain on */
    int   pos;   /* position in chain            */
};

int main(void)
{
    size_t n, m, i, j, len, max = 0;

    if (scanf("%zu %zu\n", &m, &n) < 2)
        return 1;

    Node field[n][m], *p, *first;
    char buf[m + 2]; /* newline + null byte */

    for (i = 0; i < n && fgets(buf, sizeof(buf), stdin); i++) {
        if (strlen(buf) != m + 1 || buf[m] != '\n')
            return 2; /* not enough or too many arrows */

        for (j = 0; j < m; j++) {
            size_t a = (n + i - (buf[j] == '^') + (buf[j] == 'v')) % n;
            size_t b = (m + j - (buf[j] == '<') + (buf[j] == '>')) % m;
            field[i][j] = (Node){ &field[a][b], NULL, 0 };

            if (i == a && j == b)
                return 3; /* not an arrow */
        }
    }
    if (i != n || getchar() != EOF)
        return 4; /* not enough or too many lines */

    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            /* once we hit a node with p->pos != 0 we either completed a cycle
             * or hit a node that was visited in a previous traversal. if
             * p->first is the first node we started on, we have a new cycle.
             * the cycle length is the length of the chain - the position in
             * the chain of this node. */
            for (p = first = &field[i][j], len = 1; !p->pos; p = p->next, len++) {
                p->first = first;
                p->pos   = len;
            }
            if (p->first == first && len - p->pos > max)
                max = len - p->pos;
        }
    }
    printf("max cycle %zu\n", max);
    return 0;
}