Untitled

using System.Runtime.CompilerServices;

namespace NumberMatchSolver;

public static class MatchFinder
{
    private static readonly List<(int row, int col)>[] NumberCoordinates = new List<(int row, int col)>[10];
    private static readonly List<(int row1, int col1, int row2, int col2, int number)> ConnectedPairs = new (100);
    
    static MatchFinder()
    {
        for (int digit = 0; digit < 10; digit++)
        {
            NumberCoordinates[digit] = new List<(int row, int col)>(20);
        }
    }

    public static List<(int row1, int col1, int row2, int col2, int number)> Solve(int[][] grid)
    {
        if (grid == null || grid.Length == 0) 
            return new List<(int row1, int col1, int row2, int col2, int number)>();
        
        int totalRows = grid.Length;
        int totalCols = grid[0].Length;
        
        for (int digit = 1; digit <= 9; digit++)
        {
            NumberCoordinates[digit].Clear();
        }
        
        for (int row = 0; row < totalRows; row++)
        {
            for (int col = 0; col < totalCols; col++)
            {
                int cellValue = grid[row][col];
                if (cellValue >= 1 && cellValue <= 9)
                {
                    NumberCoordinates[cellValue].Add((row, col));
                }
            }
        }
        
        ConnectedPairs.Clear();
        
        for (int digit = 1; digit <= 9; digit++)
        {
            var positions = NumberCoordinates[digit];
            int totalPositions = positions.Count;
            
            for (int firstIndex = 0; firstIndex < totalPositions - 1; firstIndex++)
            {
                var firstPosition = positions[firstIndex];
                
                for (int secondIndex = firstIndex + 1; secondIndex < totalPositions; secondIndex++)
                {
                    var secondPosition = positions[secondIndex];
                    
                    if (CanConnect(grid, firstPosition.row, firstPosition.col, secondPosition.row, secondPosition.col, totalRows, totalCols))
                    {
                        ConnectedPairs.Add((firstPosition.row, firstPosition.col, secondPosition.row, secondPosition.col, digit));
                    }
                }
            }
        }
        
        return new List<(int row1, int col1, int row2, int col2, int number)>(ConnectedPairs);
    }
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static bool CanConnect(int[][] grid, int startRow, int startCol, int endRow, int endCol, int totalRows, int totalCols)
    {
        int rowDifference = endRow - startRow;
        int colDifference = endCol - startCol;
        
        if (rowDifference != 0 && colDifference != 0)
        {
            int absRowDiff = rowDifference < 0 ? -rowDifference : rowDifference;
            int absColDiff = colDifference < 0 ? -colDifference : colDifference;
            if (absRowDiff != absColDiff) return false;
        }
        
        int rowStep = rowDifference == 0 ? 0 : (rowDifference > 0 ? 1 : -1);
        int colStep = colDifference == 0 ? 0 : (colDifference > 0 ? 1 : -1);
        
        int currentRow = startRow + rowStep;
        int currentCol = startCol + colStep;
        
        while (currentRow != endRow || currentCol != endCol)
        {
            if ((uint)currentRow >= (uint)totalRows || (uint)currentCol >= (uint)totalCols)
                return false;
            
            if (grid[currentRow][currentCol] != 0)
                return false;
            
            currentRow += rowStep;
            currentCol += colStep;
        }
        
        return true;
    }
}