import sys

def traverse(room: list[list[str]], guard_current_row: int, guard_current_col: int, direct: tuple[int, int], check_for_loop: bool) -> bool:
    row_count = len(room)
    col_count = len(room[0])
    previous_directions: list[list[list[tuple[int, int]]]] = []
    for _ in range(row_count):
        previous_directions.append([])
        for _ in range(col_count):
            previous_directions[-1].append([])

    while True:
        if not check_for_loop:
            room[guard_current_row][guard_current_col] = "X"
        else:
            if direct in previous_directions[guard_current_row][guard_current_col]:
                return True

            previous_directions[guard_current_row][guard_current_col].append(direct)

        new_row_idx = guard_current_row + direct[0]
        new_col_idx = guard_current_col + direct[1]

        if new_row_idx < 0 or new_row_idx >= row_count or new_col_idx < 0 or new_col_idx >= col_count:
            break

        if room[new_row_idx][new_col_idx] == "#":
            dir_idx = directions.index(direct)
            if dir_idx == len(directions) - 1:
                dir_idx = 0
            else:
                dir_idx += 1
            direct = directions[dir_idx]
        else:
            guard_current_row = new_row_idx
            guard_current_col = new_col_idx

    return False

lines = []
with open("input") as f:
    for line in f.readlines():
        lines.append(list(line.strip()))

found_guard = False
guard_row_idx = None
guard_col_idx = None
direction = None

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for line_idx, line in enumerate(lines):
    for icon_idx, guard_icon in enumerate(("^", ">", "v", "<")):
        if guard_icon in line:
            guard_row_idx = line_idx
            guard_col_idx = line.index(guard_icon)
            direction = directions[icon_idx]
            found_guard = True
            break

    if found_guard:
        break

if not found_guard:
    sys.exit("Could not found guard.")

traverse(lines, guard_row_idx, guard_col_idx, direction, False)

count = 0
for row_idx, line in enumerate(lines):
    for col_idx, char in enumerate(line):
        if char == "X":
            lines[row_idx][col_idx] = "#"
            if traverse(lines, guard_row_idx, guard_col_idx, direction, True):
                count += 1
            lines[row_idx][col_idx] = "X"

print(count)