const std = @import("std");
const mecha = @import("mecha");
const print = std.debug.print;

pub fn solve(part: []u8, buffer: []u8, allocator: std.mem.Allocator) !void {
    if (std.mem.eql(u8, part, "1")) {
        try part1(buffer, allocator);
    } else {
        try part2(buffer, allocator);
    }
}

fn dfs(grid: []const []const usize, row: i32, col: i32, previous: i32, seen: [][]bool) !i32 {
    if (row >= 0 and row < grid.len and col >= 0 and col < grid.len and !seen[@intCast(row)][@intCast(col)]) {
        const value = grid[@intCast(row)][@intCast(col)];

        if (previous + 1 != value) return 0;
        seen[@intCast(row)][@intCast(col)] = true;

        if (value == 9) {
            return 1;
        }

        var out: i32 = 0;
        out += try dfs(grid, row + 1, col, @intCast(value), seen);
        out += try dfs(grid, row - 1, col, @intCast(value), seen);
        out += try dfs(grid, row, col + 1, @intCast(value), seen);
        out += try dfs(grid, row, col - 1, @intCast(value), seen);
        return out;
    } else {
        return 0;
    }
}

fn part1(buffer: []const u8, allocator: std.mem.Allocator) !void {
    var lines = std.mem.splitScalar(u8, buffer, '\n');
    const width = lines.next().?.len;

    lines.reset();

    var grid: [][]usize = try allocator.alloc([]usize, width);
    defer allocator.free(grid);

    for (0..width) |i| {
        grid[i] = try allocator.alloc(usize, width);
        @memset(grid[i], 0);
    }

    var row: usize = 0;
    while (lines.next()) |line| {
        if (line.len == 0) break;
        for (line, 0..) |item, col| {
            if (item == '.') {
                grid[row][col] = 15;
            } else {
                grid[row][col] = item - '0';
            }
        }
        row += 1;
    }

    var out: i32 = 0;
    for (0..width) |r| {
        for (0..width) |c| {
            if (grid[r][c] == 0) {
                var seen: [][]bool = try allocator.alloc([]bool, width);
                defer allocator.free(seen);
                for (0..width) |i| {
                    seen[i] = try allocator.alloc(bool, width);
                    @memset(seen[i], false);
                }

                out += try dfs(grid, @intCast(r), @intCast(c), -1, seen);

                for (0..width) |i| {
                    allocator.free(seen[i]);
                }
            }
        }
    }

    for (0..width) |i| {
        allocator.free(grid[i]);
    }
    print("{d}\n", .{out});
}

//-------------------------PART2-----------------------------------------

fn dfs2(lookup: [][]i32, grid: []const []const usize, row: i32, col: i32, previous: i32) !i32 {
    if (row >= 0 and row < grid.len and col >= 0 and col < grid.len) {
        const value = grid[@intCast(row)][@intCast(col)];
        const look = lookup[@intCast(row)][@intCast(col)];

        if (previous + 1 != value) return 0;

        if (look > 0) return look;

        if (value == 9) {
            return 1;
        }

        lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row + 1, col, @intCast(value));
        lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row - 1, col, @intCast(value));
        lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row, col + 1, @intCast(value));
        lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row, col - 1, @intCast(value));

        return lookup[@intCast(row)][@intCast(col)];
    } else {
        return 0;
    }
}

fn part2(buffer: []const u8, allocator: std.mem.Allocator) !void {
    var lines = std.mem.splitScalar(u8, buffer, '\n');
    const width = lines.next().?.len;

    lines.reset();

    var grid: [][]usize = try allocator.alloc([]usize, width);
    defer allocator.free(grid);

    for (0..width) |i| {
        grid[i] = try allocator.alloc(usize, width);
        @memset(grid[i], 0);
    }

    var row: usize = 0;
    while (lines.next()) |line| {
        if (line.len == 0) break;
        for (line, 0..) |item, col| {
            if (item == '.') {
                grid[row][col] = 15;
            } else {
                grid[row][col] = item - '0';
            }
        }
        row += 1;
    }

    var out: i32 = 0;
    const lookup: [][]i32 = try allocator.alloc([]i32, width);
    for (0..width) |i| {
        lookup[i] = try allocator.alloc(i32, width);
    }
    defer allocator.free(lookup);
    for (0..width) |r| {
        for (0..width) |c| {
            if (grid[r][c] == 0) {
                out += try dfs2(
                    lookup,
                    grid,
                    @intCast(r),
                    @intCast(c),
                    -1,
                );
            }
        }
    }

    for (0..width) |i| {
        allocator.free(lookup[i]);
        allocator.free(grid[i]);
    }
    print("{d}\n", .{out});
}