var lines = File.ReadAllLines("input.txt");
var grid = CreateGrid(lines);

int[][] directions = new int[][] 
{
    [-1, 0],
    [0, -1],
    [0, 1],
    [1, 0]
};

var part1 = Part1(grid, directions);

Console.WriteLine($"Part1: {part1}\n");

int Part1(char[,] grid, int[][] directions)
{
    var rows = grid.GetLength(0);
    var columns = grid.GetLength(1);
    var neighbourDictionary = new Dictionary<(int, int), HashSet<(int, int)>>();

    for (var i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
        {
            neighbourDictionary[(i, j)] = new HashSet<(int, int)>();

            foreach (var dir in directions)
            {
                var di = dir[0];
                var dj = dir[1];

                if (i + di >= 0 && i + di < rows && j + dj >= 0 && j + dj < columns)
                {
                    if (grid[i, j] == grid[i + di, j + dj])
                    {
                        neighbourDictionary[(i, j)].Add((i + di, j + dj));
                    }
                }
            }
        }
    }
    
    var regions = new List<HashSet<(int, int)>>();
    var remainingPoints = new HashSet<(int, int)>();

    for (var i = 0; i < rows; i++)
    {
        for (var j = 0; j < columns; j++)
        {
            remainingPoints.Add((i, j));
        }
    }

    while (remainingPoints.Count > 0)
    {
        var point = remainingPoints.First();
        remainingPoints.Remove(point);

        var region = GetRegion(point, neighbourDictionary);
        regions.Add(region);
        remainingPoints.ExceptWith(region);
    }
    
    return regions.Sum(region => Perimeter(region, neighbourDictionary) * region.Count);
}

HashSet<(int, int)> GetRegion((int, int) point, Dictionary<(int, int), HashSet<(int, int)>> neighbourDict)
{
    var region = new HashSet<(int, int)>();
    var remaining = new HashSet<(int, int)> { point };

    while (remaining.Count > 0)
    {
        var curPoint = remaining.First();
        remaining.Remove(curPoint);
        region.Add(curPoint);

        var newRemaining = neighbourDict[curPoint].Except(region);
        remaining.UnionWith(newRemaining);
    }

    return region;
}

int Perimeter(HashSet<(int, int)> region, Dictionary<(int, int), HashSet<(int, int)>> neighbourDict)
{
    return region.Sum(point => 4 - neighbourDict[point].Count);
}

char[,] CreateGrid(string[] lines)
{
    var grid = new char[lines.Length, lines[0].Length];

    for (int i = 0; i < lines.Length; i++)
    {
        for (int j = 0; j < lines[i].Length; j++)
        {
            grid[i, j] = lines[i][j];
        }
    }

    return grid;
}