Maze Solver using Python

from collections import deque
import sys

class Solution:

    def bfs(self, s, e):
        n = len(self.grid)
        m = len(self.grid[0])
        queue = deque()
        N = 10**3
        visited = [[False]*N for _ in range(N)]
        moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        dist = [[0]*N for _ in range(N)]
        visited[s[0]][s[1]] = 1;
        queue.append(s)
        d = 0
        is_valid = lambda n, m, nxt: ((0<=nxt[0])and(nxt[0]<n))and((0<=nxt[1])and(nxt[1]<m))
        while queue:
            node = queue.popleft()
            for move in moves:
                nxt = (move[0]+node[0], move[1]+node[1])
                if is_valid(n, m, nxt):
                    if not visited[nxt[0]][nxt[1]] and self.grid[nxt[0]][nxt[1]]!='X':
                        if nxt[0]==e[0] and nxt[1]==e[1]:
                            return 1+dist[node[0]][node[1]]
                        else:
                            visited[nxt[0]][nxt[1]] = True
                            dist[nxt[0]][nxt[1]] = 1+dist[node[0]][node[1]]
                            queue.append(nxt)
        return -1

    def main(self):
        self.grid = []
        row = input()
        while row:
            self.grid.append(list(row))
            row = input()
        n = len(self.grid)
        m = len(self.grid[0])
        for i in range(n):
            if self.grid[i][0] == ' ':
                s = (i, 0)
            if self.grid[i][m-1] == ' ':
                e = (i, m-1)
        for i in range(n):
            for j in range(m):
                if self.grid[i][j] == '*':
                    k = (i, j)
                    break
        toKey = self.bfs(s, k)
        if toKey == -1:
            print(-1)
            return
        toExit = self.bfs(k, e)
        if toExit==-1:
            print(-2)
            return
        print(toKey+toExit)

if __name__ == "__main__":
    input = lambda : sys.stdin.buffer.readline().decode().strip('\n')
    sol = Solution()
    sol.main()