# Q3


n = int(input("Enter grid size (at least 8): "))
sr = int(input("Start row: "))
sc = int(input("Start column: "))
gr = int(input("Goal row: "))
gc = int(input("Goal column: "))

obs = set()
for i in range(int(input("Number of obstacles: "))):
    r = int(input("Obstacle row: "))
    c = int(input("Obstacle column: "))
    obs.add((r, c))

q = [(abs(sr-gr)+abs(sc-gc), 0, sr, sc, [(sr,sc)])]
visited = []

while q:
    q.sort()
    f, g, r, c, path = q.pop(0)

    if (r, c) in visited:
        continue
    visited.append((r, c))

    if (r, c) == (gr, gc):
        print("Path:", path)
        print("Path length:", g)
        print("Cells explored:", len(visited))

        for i in range(n):
            for j in range(n):
                if (i, j) == (sr, sc):
                    print("S", end=" ")
                elif (i, j) == (gr, gc):
                    print("G", end=" ")
                elif (i, j) in obs:
                    print("#", end=" ")
                elif (i, j) in path:
                    print("*", end=" ")
                else:
                    print(".", end=" ")
            print()
        break

    for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
        if 0 <= nr < n and 0 <= nc < n:
            if (nr,nc) not in obs and (nr,nc) not in visited:
                ng = g + 1
                h = abs(nr-gr) + abs(nc-gc)
                q.append((ng+h, ng, nr, nc, path+[(nr,nc)]))
else:
    print("No path found")







