Untitled

using System.Runtime.CompilerServices;

namespace NumberMatchSolver;

public static class MatchFinder
{
    private static readonly List<(int r, int c)>[] NumberPositions = new List<(int r, int c)>[10];
    private static readonly List<(int r1, int c1, int r2, int c2, int number)> ResultPairs = new List<(int r1, int c1, int r2, int c2, int number)>(100);
    
    static MatchFinder()
    {
        for (int i = 0; i < 10; i++)
        {
            NumberPositions[i] = new List<(int r, int c)>(20);
        }
    }

    public static List<(int r1, int c1, int r2, int c2, int number)> Solve(int[][] grid)
    {
        if (grid == null || grid.Length == 0) 
            return new List<(int r1, int c1, int r2, int c2, int number)>();
        
        int rows = grid.Length;
        int cols = grid[0].Length;
        
        for (int i = 1; i <= 9; i++)
        {
            NumberPositions[i].Clear();
        }
        
        for (int r = 0; r < rows; r++)
        {
            for (int c = 0; c < cols; c++)
            {
                int num = grid[r][c];
                if (num >= 1 && num <= 9)
                {
                    NumberPositions[num].Add((r, c));
                }
            }
        }
        
        ResultPairs.Clear();
        
        for (int num = 1; num <= 9; num++)
        {
            var positions = NumberPositions[num];
            int count = positions.Count;
            
            for (int i = 0; i < count - 1; i++)
            {
                var pos1 = positions[i];
                
                for (int j = i + 1; j < count; j++)
                {
                    var pos2 = positions[j];
                    
                    if (CanConnect(grid, pos1.r, pos1.c, pos2.r, pos2.c, rows, cols))
                    {
                        ResultPairs.Add((pos1.r, pos1.c, pos2.r, pos2.c, num));
                    }
                }
            }
        }
        
        return new List<(int r1, int c1, int r2, int c2, int number)>(ResultPairs);
    }
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static bool CanConnect(int[][] grid, int r1, int c1, int r2, int c2, int rows, int cols)
    {
        int deltaR = r2 - r1;
        int deltaC = c2 - c1;
        
        if (deltaR != 0 && deltaC != 0)
        {
            int absR = deltaR < 0 ? -deltaR : deltaR;
            int absC = deltaC < 0 ? -deltaC : deltaC;
            if (absR != absC) return false;
        }
        
        int stepR = deltaR == 0 ? 0 : (deltaR > 0 ? 1 : -1);
        int stepC = deltaC == 0 ? 0 : (deltaC > 0 ? 1 : -1);
        
        int currentR = r1 + stepR;
        int currentC = c1 + stepC;
        
        while (currentR != r2 || currentC != c2)
        {
            if ((uint)currentR >= (uint)rows || (uint)currentC >= (uint)cols)
                return false;
            
            if (grid[currentR][currentC] != 0)
                return false;
            
            currentR += stepR;
            currentC += stepC;
        }
        
        return true;
    }
}