find min dis with one time teleport

'''
this is an easy version
where there is only portal type A
in the hard version you will have multiple portal chars

you are given a matrix with empty cells(.) obstacle cells(#)
and teleportation cells (A)
you can use the teleportation at max 1 time
in your journey ,the teleportation does not count as a move
find the min moves you need to travel from 0,0 to m-1,n-1

============================================================================================================================================

here it said you can travel through portal at max one time
this is boon for us

so you just need to start multiBFS from all the teleportation points
to find minDisFromStart
and also another multiBFS from all teleportation points to find mindDisToEnd
so just add both dis you will get the ans

but wait there is no rule to definitely use teleportation right
so do a simple BFS from start to end without any teleportation
and decide the final answer
'''
from collections import defaultdict,deque
class Solution:

    def isValid(self,currx,curry,m,n):
        return 0<=currx<m and 0<=curry<n

    def bfs(self,q,targetx,targety,seen,m,n,mat):
        minDis = 10**10

        while len(q):
            curr = q.popleft()
            xaxis = [-1,0,0,1]
            yaxis = [0,-1,1,0]
            for i in range(4):
                currx = curr[0][0] + xaxis[i]
                curry = curr[0][1] + yaxis[i]
                if not self.isValid(currx,curry,m,n):
                    continue
                if (currx,curry) in seen:
                    continue
                if mat[currx][curry] == '#':
                    continue
                newDis = curr[1]+1
                if currx == targetx and curry == targety:
                    minDis = min(minDis,newDis)
                else:
                    q.append([(currx,curry),newDis])
                    seen.add((currx,curry))

        return minDis

    def calculateMindisToReachInMatrix(self,mat):
        #lets grab all the teleportaion points and start a multi source BFS for start and end points
        m = len(mat)
        n  = len(mat[0])
        q = deque()
        seen = set()

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 'A':
                    q.append([(i,j),0])
                    seen.add((i,j))
        minStartDis = self.bfs(q.copy(),0,0,seen.copy(),m,n,mat)
        minEndDis = self.bfs(q.copy(),m-1,n-1,seen.copy(),m,n,mat)

        if mat[0][0] == 'A':
            minStartDis = 0
        if mat[m-1][n-1] == 'A':
            minEndDis = 0

        q2 = deque()
        q2.append([(0,0),0])
        seen2 = set()
        seen2.add((0,0))
        minDirectDis = self.bfs(q2.copy(),m-1,n-1,seen2.copy(),m,n,mat)
        print(f"minStartDis {minStartDis} minEndDis {minEndDis} minDirectDis {minDirectDis}")
        return min(minStartDis+minEndDis,minDirectDis)#mindis with teleportation and without teleportation


def main():
    solution = Solution()

    # Test cases: (matrix, expected_min_moves, description)
    test_cases = [
        (
            [
                ['A', '.', '.'],
                ['.', 'A', '.'],
                ['.', '.', '.']
            ],
            2,
            "3x3 without obstacles - portal might help"
        ),

         (
            [
                ['.', '#', '.', '.','.'],
                ['.', '#', '.', '#','.'],
                ['.', '#', '.', '#','.'],
                ['.', '.', '.', '#','.'],
            ],
            13,
            "4x5 with two portals and obstacles"
        ),
        (
            [
                ['.', '.', '.'],
                ['.', 'A', '.'],
                ['.', '.', '.']
            ],
            4,
            "Simple 3x3 with portal in center - direct path better"
        ),
        (
            [
                ['.', '#', '.'],
                ['.', 'A', '#'],
                ['.', '.', '.']
            ],
            4,
            "3x3 with obstacles - portal might help"
        ),
        (
            [
                ['.', '.', '.', '.'],
                ['.', 'A', '#', '.'],
                ['.', '#', 'A', '.'],
                ['.', '.', '.', '.']
            ],
            4,
            "4x4 with two portals and obstacles"
        ),

    ]

    print("Running test cases...\n")
    passed = 0
    failed = 0

    for i, (matrix, expected, description) in enumerate(test_cases, 1):
        try:
            result = solution.calculateMindisToReachInMatrix(matrix)
            status = "✓ PASS" if result == expected else "✗ FAIL"

            if result == expected:
                passed += 1
            else:
                failed += 1

            print(f"Test {i}: {status}")
            print(f"  Matrix: {len(matrix)}x{len(matrix[0])}")
            print(f"  Description: {description}")
            print(f"  Expected: {expected}, Got: {result}")

            # Show matrix structure
            print(f"  Grid:")
            for row in matrix:
                print(f"    {' '.join(row)}")
        except Exception as e:
            failed += 1
            print(f"Test {i}: ✗ ERROR")
            print(f"  Matrix: {len(matrix)}x{len(matrix[0])}")
            print(f"  Description: {description}")
            print(f"  Error: {e}")
        print()

    print(f"Results: {passed} passed, {failed} failed out of {len(test_cases)} tests")


if __name__ == "__main__":
    main()